poj3680 Intervals -電腦資料

    IntervalsTime Limit:5000MSMemory Limit:65536KTotal Submissions:7161Accepted:2982

    Description

    You are givenNweighted open intervals. Theith interval covers (a_i,b_i) and weighsw_i. 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 integersa_i,b_i,w_i(1 ≤a_i<b_i≤ 100,000, 1 ≤w_i≤ 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

    費用流，構圖方法很巧妙，

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>