程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj3680 Intervals

poj3680 Intervals

編輯：關於C++

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

Description

You are given N weighted open intervals. The ith interval covers (a_i, b_i) and weighs w_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 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 a_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

4

3 1
1 2 2
2 3 4
3 4 8

3 1
1 3 2
2 3 4
3 4 8

3 1
1 100000 100000
1 2 3
100 200 300

3 2
1 100000 100000
1 150 301
100 200 300

Sample Output

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);
	}
}