Tang-Dreamoon's Blog

poj 3680 最小费用最大流

发表于 | 分类于 ， ，

哈哈哈哈！还没调就A了！

　　题目链接：poj 3680

　　题意：给定 N 个带权值的开区间，第 i 个区间覆盖（Ai，Bi），权值为 Wi 。现在要你挑选出一些区间使得总权值最大，并且满足实数轴上任意一个点被覆盖不超过 K 次。

　　题解：既然这是实数轴，那么肯定不可能把所有的点都表示出来，显然一个区间的两个端点可以代表这个区间内的所有的点。既然任何一个点被覆盖不超过 K 次，那么我们把每一个点都拆成入点和出点，入点向出点连一条容量为 K 的边，表示每一个点只能被覆盖 K 次。然后我们还要把数轴上所有的点建立联系，所以我们从当前点的出点向后一个点的入点连一条容量为正无穷的边。而对于每一个区间（L，R）我们从 L 到 R 连一条容量为1、权值为 Wi 的边，因为每一个区间显然只能选择一次。最后跑一发最小费用最大流就好了。

　　我思故我在：(⊙o⊙)…额，写最小费用最大流的时候，要注意反向边的权值显然为正向边权值的相反数，一定要记住啊！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,k;
int tot=0,T;
struct table{
	int to,id,val;
};
vector<table> ve[888];
struct node{
	int l,r,val;
}map[233];
int f[4000];
int stack[888];
int mina[888],dis[888],fa[888],from[888];
bool vis[888];
bool bfs()
{
	memset(dis,0x3f,sizeof(dis));
	memset(mina,0x3f,sizeof(mina));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	dis[0]=0,vis[0]=1,mina[0]=247483647;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(dis[y.to]>dis[x]+y.val&&f[y.id]>0)
			{
				dis[y.to]=dis[x]+y.val;
				mina[y.to]=min(mina[x],f[y.id]);
				fa[y.to]=y.id;
				from[y.to]=x;
				if(!vis[y.to])
				{
					vis[y.to]=1,q.push(y.to);
				}
			}
		}
	}
	return  dis[T]!=1061109567;
}
int zeng()
{
	for(int i=T;i;i=from[i])
	{
		f[fa[i]]-=mina[T];
		f[fa[i]^1]+=mina[T];
	}
	return mina[T]*dis[T];
}
int dinic()
{
	int ans=0;
	while(bfs())
	{
		ans+=zeng();
	}
	return ans;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		int head=0;
		for(int i=1;i<=n;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			stack[++head]=x;
			stack[++head]=y;
			map[i].l=x,map[i].r=y,map[i].val=z;
		}
		sort(stack+1,stack+1+head);
		head=unique(stack+1,stack+1+head)-stack-1;
		for(int i=1;i<=n;i++)
		{
			int x=lower_bound(stack+1,stack+1+head,map[i].l)-stack;
			int y=lower_bound(stack+1,stack+1+head,map[i].r)-stack;
			int z=map[i].val;
			ve[x+head+1].push_back((table){y,tot,-z}),f[tot++]=1;
			ve[y].push_back((table){x+head+1,tot,z}),f[tot++]=0;
			ve[0].push_back((table){x,tot,0}),f[tot++]=247483647;
			ve[x].push_back((table){0,tot,0}),f[tot++]=0;
		}
		for(int i=1;i<=head;i++)
		{
			ve[i].push_back((table){i+head+1,tot,0}),f[tot++]=k;
			ve[i+head+1].push_back((table){i,tot,0}),f[tot++]=0;
			ve[i+head+1].push_back((table){i+1,tot,0}),f[tot++]=247483647;
			ve[i+1].push_back((table){i+head+1,tot,0}),f[tot++]=0;
		}
		T=head+1;
		printf("%d\n",-dinic());
		tot=0;
		for(int i=0;i<=head*2+2;i++) ve[i].clear();
	}
	return 0;
 }