POJ 3680 - Intervals

Intervals

Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 9725 Accepted: 4185

Description

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

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

14
12
100000
100301

费用流经典题目。

因为每个点不能被题目给的开区间覆盖k次，所以我们限制S出去的流量为k，并且 i -> i+1 的流量为inf，保证最大流一定为k，对于每个区间，之间连边费用为 - w ，即可。

这道题目因为点比较多，但是涉及到的点不多，所以我们需要离散化。

和志愿者招募比较类似。

AC代码：

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=410,M=1e6+10;
int T,n,k,x[N],y[N],z[N],s,t=401,d[N],st[N],vis[N],res;
int head[N],nex[M],to[M],w[M],flow[M],tot;	
queue<int> q;	vector<int> v;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,0,-d);}
inline void init(){
	tot=1;	memset(head,0,sizeof head); v.clear(); res=0;
}
inline int spfa(){
	memset(st,0,sizeof st); q.push(s); vis[s]=1; memset(d,inf,sizeof d); d[s]=0;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]<inf;
}
int dfs(int x,int f){
	if(x==t)	return res+=f*d[t],f;
	st[x]=1;	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(flow[i]&&!st[to[i]]&&d[to[i]]==d[x]+w[i]){
			int mi=dfs(to[i],min(f,flow[i]));
			flow[i]-=mi,flow[i^1]+=mi,fl+=mi,f-=mi;
		}
	}
	return fl;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&k);	init();
		for(int i=1;i<=n;i++){
			scanf("%d %d %d",&x[i],&y[i],&z[i]);
			v.push_back(x[i]),v.push_back(y[i]);
		}
		sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
		for(int i=1;i<=n;i++){
			x[i]=lower_bound(v.begin(),v.end(),x[i])-v.begin()+1;
			y[i]=lower_bound(v.begin(),v.end(),y[i])-v.begin()+1;
			add(x[i],y[i],1,-z[i]);
		}
		for(int i=0;i<v.size()-1;i++)	add(i+1,i+2,inf,0);
		add(s,1,k,0);	add(v.size(),t,k,0);
		while(spfa())	dfs(s,inf);
		printf("%d\n",-res);
	}
	return 0;
}