题目链接:http://poj.org/problem?id=3680
题目大意:有N个带权开区间,让你从中选择一些使得权值最大,实数轴上任意一点被覆盖不超过K次,输出最大权值和。
思路: 经典的在区间上建图题目。首先把所有端点离散化编号从1到n,建立源点0,汇点n+1。对于除汇点之外的点建立从i到i+1的边,容量为K,费用为0。对于每个区间(l,r),建立从l′到r′的边,容量为1,费用为−wi。跑一遍最小费用最大流,结果的相反数即为答案。
#include <bits/stdc++.h> #define LL long long using namespace std; const LL maxn=500; const LL maxm=1e6+10; struct Mcmf_flow{ bool vis[maxn]; LL dis[maxn]; LL pre[maxn]; LL last[maxn]; LL flow[maxn]; LL zdl, fy; LL s1[maxn];//sum的前缀和 LL sum[maxn];//流量为i的最小费用 LL tot; //dis最小花费;pre每个点的前驱;last每个点的所连的前一条边;flow源点到此处的流量 struct Edge { LL to,next,flow,dis;//flow流量 dis花费 } e[maxm<<1]; LL head[maxn],cut; queue <LL> q; int N; void init(int n){ N=n+5; memset(s1, 0, sizeof(LL)*(N+60)); memset(sum, 0, sizeof(LL)*(N+60)); memset(head,-1,sizeof(LL)*(N+60)); tot=0; cut=-1;//初始化 zdl=fy=0; } void add_e(LL from,LL to,LL flow,LL dis) { e[++cut].next=head[from]; e[cut].to=to; e[cut].flow=flow; e[cut].dis=dis; head[from]=cut; } void add(LL x, LL y, LL z, LL f){ add_e(x,y,z,f); add_e(y,x,0,-f); } bool spfa(LL s,LL t) { memset(dis,0x7f,sizeof(LL)*(N+60)); memset(flow,0x7f,sizeof(LL)*(N+60)); memset(vis,0,sizeof(bool)*(N+60)); q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1; while (!q.empty()) { LL now=q.front(); q.pop(); vis[now]=0; for (LL i=head[now]; i!=-1; i=e[i].next) { if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].dis) { //正边 dis[e[i].to]=dis[now]+e[i].dis; pre[e[i].to]=now; last[e[i].to]=i; flow[e[i].to]=min(flow[now],e[i].flow);// if (!vis[e[i].to]) { vis[e[i].to]=1; q.push(e[i].to); } } } } return pre[t]!=-1; } void MCMF(LL s, LL t) { while (spfa(s,t)) { LL now=t; zdl+=flow[t]; fy+=flow[t]*dis[t]; sum[++tot]=fy;//得到sum[] s1[tot]=sum[tot]-sum[tot-1];//得到s1[] while (now!=s) { //从源点一直回溯到汇点 e[last[now]].flow-=flow[t];//flow和dis容易搞混 e[last[now]^1].flow+=flow[t]; now=pre[now]; } } } }min_Flow; int L[205], R[205], w[205], a[500], tot=0; int main() { int t; scanf("%d", &t); while(t--){ tot=0; int n, k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++){ scanf("%d%d%d", &L[i], &R[i], &w[i]); a[++tot]=L[i]; a[++tot]=R[i]; } sort(a+1, a+tot+1); int cnt=unique(a+1, a+tot+1)-a-1; for(int i=1; i<=n; i++){ L[i]=lower_bound(a+1, a+cnt+1, L[i])-a; R[i]=lower_bound(a+1, a+cnt+1, R[i])-a; } int S=0, T=cnt+1; min_Flow.init(T); for(int i=S; i<T; i++){ min_Flow.add(i, i+1, k, 0); } for(int i=1; i<=n; i++){ min_Flow.add(L[i], R[i], 1, -w[i]); } min_Flow.MCMF(S, T); printf("%d\n", -min_Flow.fy); } return 0; }