Ryan_<

Description

Input

Output

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