网络流|poj3680 Intervals OIer的狂欢|好题

Intervals

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 7161		Accepted: 2982

Description
【网络流|poj3680 Intervals】You are given N weighted open intervals. The ith interval covers (ai, bi) and weighs wi. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.
Input
The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers ai, bi, wi(1 ≤ ai < bi ≤ 100,000, 1 ≤ wi ≤ 100,000) describing the intervals.
There is a blank line before each test case.
Output
For each test case output the maximum total weights in a separate line.
Sample Input

43 1 1 2 2 2 3 4 3 4 83 1 1 3 2 2 3 4 3 4 83 1 1 100000 100000 1 2 3 100 200 3003 2 1 100000 100000 1 150 301 100 200 300

Sample Output

14 12 100000 100301

Source
POJ Founder Monthly Contest – 2008.07.27, windy7926778

费用流，构图方法很巧妙。
我一开始的想法是区间放左边，点放右边，跑费用流。后来发现显然是错的，因为在最大流时源点流入区间的边不一定满流，也就是一个区间内的点没有全部覆盖，这显然是错误的。
下面是正确地做法：要保证每个点最多覆盖k次，可以把所有点串联起来，每个点向后一个点连一条容量k、费用0的边。(是不是很机智啊！！)然后对于区间[a,b]，从a到b连一条容量1、费用w的边就可以了。最后从源点到1点、从n点到汇点，分别连一条容量k、费用0的点。
至于这个方法的正确性如何证明呢？？我可以说只可意会不可言传吗=_=……大家自己脑补吧……额
如此看来，构图真是一种艺术啊！

#include #include #include #include #include #include #include #include #define F(i,j,n) for(int i=j; i<=n; i++) #define D(i,j,n) for(int i=j; i>=n; i--) #define LL long long #define pa pair #define maxn 1000 #define maxm 1000 #define inf 1000000000 using namespace std; int tt,n,k,s,t,cnt,ans,tot; int head[maxn],dis[maxn],p[maxn],a[maxn],b[maxn],w[maxn],f[maxn]; bool inq[maxn]; map mp; struct edge_type { int from,to,next,v,c; }e[maxm]; inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar(); } return x*f; } inline void add_edge(int x,int y,int v,int c) { e[++cnt]=(edge_type){x,y,head[x],v,c}; head[x]=cnt; e[++cnt]=(edge_type){y,x,head[y],0,-c}; head[y]=cnt; } inline bool spfa() { queueq; memset(inq,false,sizeof(inq)); F(i,1,t) dis[i]=inf; dis[s]=0; q.push(s); inq[s]=true; while (!q.empty()) { int x=q.front(); q.pop(); inq[x]=false; for(int i=head[x]; i; i=e[i].next) { int y=e[i].to; if (e[i].v&&dis[y]>dis[x]+e[i].c) { dis[y]=dis[x]+e[i].c; p[y]=i; if (!inq[y]){q.push(y); inq[y]=true; } } } } return dis[t]!=inf; } inline void mcf() { ans=0; while (spfa()) { int tmp=inf; for(int i=p[t]; i; i=p[e[i].from]) tmp=min(tmp,e[i].v); ans+=tmp*dis[t]; for(int i=p[t]; i; i=p[e[i].from]){e[i].v-=tmp; e[i^1].v+=tmp; } } } int main() { tt=read(); while (tt--) { memset(head,0,sizeof(head)); memset(p,0,sizeof(p)); memset(f,0,sizeof(f)); cnt=1; tot=0; n=read(); k=read(); F(i,1,n) { a[i]=read(); b[i]=read(); w[i]=read(); f[2*i-1]=a[i]; f[2*i]=b[i]; } sort(f+1,f+2*n+1); F(i,1,2*n) if (i==1||f[i]!=f[i-1]) mp[f[i]]=++tot; s=tot+1; t=tot+2; F(i,1,tot-1) add_edge(i,i+1,k,0); add_edge(s,1,k,0); add_edge(tot,t,k,0); F(i,1,n) add_edge(mp[a[i]],mp[b[i]],1,-w[i]); mcf(); printf("%d\n",-ans); } }