IntervalsTime Limit:5000MSMemory Limit:65536KTotal Submissions:7161Accepted:2982
Description
You are givenNweighted open intervals. Theith interval covers (ai,bi) and weighswi. 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 thanktimes.
Input
The first line of input is the number of test case.
The first line of each test case contains two integers,NandK(1 ≤K≤N≤ 200).
The nextNline each contain three integersai,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 11 2 22 3 43 4 83 11 3 22 3 43 4 83 11 100000 1000001 2 3100 200 3003 21 100000 1000001 150 301100 200 300
Sample Output
1412100000100301
Source
POJ Founder Monthly Contest – 2008.07.27, windy7926778费用流，构图方法很巧妙，
poj3680 Intervals
。我一开始的想法是区间放左边，点放右边，跑费用流。后来发现显然是错的，因为在最大流时源点流入区间的边不一定满流，也就是一个区间内的点没有全部覆盖，这显然是错误的。
下面是正确地做法：要保证每个点最多覆盖k次，可以把所有点串联起来，每个点向后一个点连一条容量k、费用0的边。(是不是很机智啊！！)然后对于区间[a,b]，从a到b连一条容量1、费用w的边就可以了。最后从源点到1点、从n点到汇点，分别连一条容量k、费用0的点。
至于这个方法的正确性如何证明呢？？我可以说只可意会不可言传吗=_=……大家自己脑补吧……额
如此看来，构图真是一种艺术啊！
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include#include<queue>#include<map>#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<int,int>#define maxn 1000#define maxm 1000#define inf 1000000000using 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<int,int>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(){ queue<int>q; 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); }}</int></int,int></int,int></map></queue></cmath></cstring></cstdlib></cstdio></iostream>