BZOJ 1797 Mincut

发表于 | 更新于

Link

Solution

最小割的可行边和必须边

最小割

求出最大流后，从源点开始沿残量网络BFS，标记能够到达的点。 连接已标记的点和未标记的点的正向边就是该网络的一个最小割集。

必须边

性质

  1. 满流
  2. 残余网络中SS能到fromfrom、toto能到TT。

求法

SCC之后，看是否 。

可行边

性质

  1. 满流
  2. 删掉之后在残余网络中找不到u到v的路径。

求法

SCC之后，看是否 。

好吧这个还是记结论吧。。

Code

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define getc() getchar()
#define putc(x) putchar(x)
#define puts(x) printf("%s",x)
#define foreach(it,x) for(typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())

typedef long long ll;

template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}

using std::max;
using std::min;

const int INF=0X1F1F1F1F,MAXN=4000+11,MAXM=60000+11;
namespace ISAP
{
	struct Edge{int to,cap,v,pre;}e[MAXM<<1];int id[MAXN],ec=1,s,t,n;
	void Adde(int f,int t,int cap)
	{
		e[++ec].to=t;e[ec].cap=cap;e[ec].v=0;e[ec].pre=id[f];id[f]=ec;
		e[++ec].to=f;e[ec].cap=0;e[ec].v=0;e[ec].pre=id[t];id[t]=ec;
	}
	int d[MAXN],num[MAXN],pree[MAXN],arc[MAXN];
	int Aug()
	{
		int minf=INF;
		for(int i=pree[t];i;i=pree[e[i^1].to])
			chkmn(minf,e[i].cap-e[i].v);
		for(int i=pree[t];i;i=pree[e[i^1].to])
			e[i].v+=minf,e[i^1].v-=minf;
		return minf;
	}
	int MaxFlow()
	{
		memcpy(arc,id,sizeof(id));
		num[0]=n;
		int flow=0,pres=s,adv;
		while(d[s]<n)
		{
			if(pres==t)
			{
				flow+=Aug();
				pres=s;
			}
			adv=0;
			for(int &i=arc[pres];i;i=e[i].pre)
			{
				int u=e[i].to;
				if(e[i].cap>e[i].v && d[pres]==d[u]+1)
				{
					adv=1;
					pree[pres=u]=i;
					break;
				}
			}
			if(!adv)
			{
				if(--num[d[pres]]==0) break;
				arc[pres]=id[pres];
				int mind=n-1;
				for(int i=id[pres];i;i=e[i].pre)
					if(e[i].cap>e[i].v) 
						chkmn(mind,d[e[i].to]);
				num[d[pres]=mind+1]++;
				if(pres!=s) pres=e[pree[pres]^1].to;
			}
		}
		return flow;
	}	
}using namespace ISAP;
int dc,dfn[MAXN],low[MAXN],stack[MAXN],top,sc,sn[MAXN];
bool instack[MAXN];
void DFS(int pos)
{
	instack[stack[++top]=pos]=1;
	dfn[pos]=low[pos]=++dc;
	for(int i=id[pos];i;i=e[i].pre)
	{
		if(e[i].cap==e[i].v) continue;
		int u=e[i].to;
		if(!dfn[u])
		{
			DFS(u);
			chkmn(low[pos],low[u]);
		}
		else if(instack[u])
			chkmn(low[pos],dfn[u]);
	}
	if(dfn[pos]==low[pos])
	{
		++sc;
		while(stack[top+1]!=pos)
		{
			sn[stack[top]]=sc;
			instack[stack[top--]]=0;
		}
	}
}
int main()
{
	freopen("input","r",stdin);
	int m;
	get(n),get(m),get(s),get(t);
	for(int i=1;i<=m;++i)
	{
		int u,v,c;get(u),get(v),get(c);
		Adde(u,v,c);
	}
	int flow=MaxFlow();
	for(int i=1;i<=n;++i)
		if(!dfn[i])
		{
			//dc=0;
			DFS(i);
		}
	for(int i=1;i<=m;++i)
	{
		if(e[i<<1].cap!=e[i<<1].v) 
		{
			puts("0 0\n");
			continue;
		}
		int to=e[i<<1].to,from=e[i<<1|1].to;//rev.
		put(sn[from]!=sn[to]),putc(' '),put(sn[s]==sn[from] && sn[t]==sn[to]),putc('\n');
	}
	return 0;
}