1
6
2016
0

【POJ3680】【费用流】Intervals

Intervals
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 7186   Accepted: 2991

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 ≤ KN ≤ 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

Source

题意:给定n个带权开区间,选择其中一些使得权值最大并且区间重叠层数不超过k。

题解:——这样的题目概括就相当于翻译,并不能体现出一道题的精髓。

其实就是选择k条路径。故需分别添加超级源和超级汇,容量由上一题的2扩展为k,添加的边费用自然是0。【注意:网络流中的边均为有向】

给定节点个数却标号分散,可知要用离散化。

以数轴上的点为节点,对于每单位长度的区间,可以选或不选,那么就连两条路径,一条费用为-w(要得到最大费用),容量为1(表示选,每个给定区间只有一个),一条费用为0,容量为inf(表示不选,自然可以多次穿过,这里赋值为k也可)。其实也不难,你说呢

总的来说,操作就是:

将区间端点离散化,

将第i个点连第i+1个点花费为0,容量为INF,即addedge(i,i+1,0,INF);

处理N个区间(ai,bi),addedge(ai,bi,-wi,1);

最后源点连第一个点,addedge(src,1,0,k);最后一个点连汇点,addedge(n,sink,0,k)。

 

手生了!!犯了很多低级错误:

  • 数据组数tt 不要和汇点t混淆
  • 源点s,t赋值为tot+1,和tot+2时注意spfa的循环赋值语句:for i:1→t
    • 赋值为0,tot+1较为方便,注意原有节点应从1开始,循环语句 for i:s→t即可
  • d[]赋值为127时return d[t]!=inf inf不可为其他值(memset按位赋值 char的值域是-128~127)
  • POJ数据范围不可靠

我的代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#define inf 1<<30
#define for2(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
const int N=1000,M=1000;
int n,k,m,tot=1,s,t,ans;
int a[N],b[N],w[N],f[N];
int head[N],d[N],p[N];
bool inq[N];
map<int,int> mp;
struct edge{
	int from,go,next,v,c;//流量,cost费用
	}e[M];
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 addedge(int x,int y,int v,int c)
{
	e[++tot]=(edge){x,y,head[x],v,c};head[x]=tot;
	e[++tot]=(edge){y,x,head[y],0,-c};head[y]=tot;
}
inline bool spfa()
{
	queue<int> q;
	memset(inq,false,sizeof(inq));
	memset(d,127,sizeof(d));
	for2(i,s,t) d[i]=inf;
	q.push(s);inq[s]=true;d[s]=0;
	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].go;
			if(e[i].v&&d[x]+e[i].c<d[y]){
				d[y]=d[x]+e[i].c;
				p[y]=i;//标记入边
				if(!inq[y]){
					q.push(y);
					inq[y]=true;
				}
			}
		}
	}
	return d[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+=d[t]*tmp;
		for(int i=p[t];i;i=p[e[i].from]){
			e[i].v-=tmp;
			e[i^1].v+=tmp;
		}
	}
}
int main()
{
	int tt;
	tt=read();
	while(tt--){
		memset(head,0,sizeof(head));
		memset(p,0,sizeof(p));
		memset(f,0,sizeof(f));
		m=0;tot=1;//每次都要清空m和tot 
		n=read();k=read();
		for2(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);
		for2(i,1,2*n) if(i==1||f[i]!=f[i-1]) mp[f[i]]=++m;
		s=0;t=m+1;
		addedge(s,1,k,0);addedge(m,t,k,0);
		for2(i,1,m-1) addedge(i,i+1,inf,0);//赋值为k或inf均可 
		for2(i,1,n) addedge(mp[a[i]],mp[b[i]],1,-w[i]);
		mcf();
		printf("%d\n",-ans);//-!
		}
	return 0;
}
Category: 网络流 | Tags: | Read Count: 229

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com