Tang-Dreamoon's Blog

poj 3204 最小割必须边

发表于 | 分类于 ， ，

最小割的可行边与必须边

　　题目链接：poj 3204

　　题意：输出一个有向图最小割的必须边的个数。

　　题解：看在我估计不会写最小割的可行边的份上，这次就把两种边的求法都写一遍把。首先说一下两种边的定义：必须边——一定在最小割中的边、扩大容量后能增大最大流的边；可行边——被某一种最小割的方案包含的边。下面来说做法：对于必须边来说满足以下条件——①满流；②残余网络中 S 能到入点、出点能到 T 。从 S 开始 D F S 、T 开始反向 D F S ，标记到达的点，然后枚举满流的边即可。对于可行边来说满足以下条件——①满流；②删掉之后在残余网络中找不到 U 到 V 的路径。一可以在残余网络中 t a r j a n 求 S c c ，二可以在残余网络中 F l o y d 一发，反正不影响复杂度 O(∩_∩)O哈哈~~~

　　我思故我在：在最后统计答案的时候我们应该列举完全所有的条件。　　一开始我在写上面那一段代码的时候就没有判断是否满流，导致 W A 的很不爽。我贴一个数据大家就明白了：
4 6
0 1 4
0 2 2
1 2 2
1 3 1
2 3 7
2 0 1
A N S ：3

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
112
113
114
115
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int tot=0;
struct table{
	int to,id;
};
vector<table> ve[50500];
vector<table> va[50500];
vector<table> vp[50500];
int color[50500];
int deep[50500];
int f[505000];
int laji[505000];
inline int min(int a,int b)
{
	return a < b ? a : b; 
}
bool bfs()
{
	memset(deep,-1,sizeof(deep));
	queue<int> q;
	deep[0]=0;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(deep[y.to]==-1&&f[y.id]>0)
			{
				deep[y.to]=deep[x]+1;
				q.push(y.to);
			}
		}
	}
	return deep[n-1]!=-1;
}
int zeng(int a,int b)
{
	if(a==n-1) return b;
	int r=0,t;
	for(int i=0;i<ve[a].size()&&b>r;i++)
	{
		table y=ve[a][i];
		if(deep[y.to]==deep[a]+1&&f[y.id]>0)
		{
			t=zeng(y.to,min(f[y.id],b-r));
			r+=t,f[y.id]-=t,f[y.id^1]+=t;
		}
	}
	if(!r) deep[a]=-1;
	return r;
}
void dinic()
{
	while(bfs())
	{
		while(zeng(0,247483647));
	}
}
void dfs1(int x)
{
	color[x]=1;
	for(int i=0;i<va[x].size();i++)
	{
		table y=va[x][i];
		if(f[y.id]>0&&color[y.to]==0) dfs1(y.to);
	}
}
void dfs2(int x)
{
	color[x]=2;
	for(int i=0;i<vp[x].size();i++)
	{
		table y=vp[x][i];
		if(f[y.id]>0&&color[y.to]==0) dfs2(y.to);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		va[x].push_back((table){y,tot});
		vp[y].push_back((table){x,tot});
		ve[x].push_back((table){y,tot}),f[tot++]=z;
		ve[y].push_back((table){x,tot}),f[tot++]=0;
	}
	dinic();
	dfs1(0);
	dfs2(n-1);
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<va[i].size();j++)
		{
			table y=va[i][j];
			if((color[y.to]^color[i])==3&&f[y.id]==0) ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}