BZOJ1797: [Ahoi2009]Mincut 最小割（洛谷P4126）

最小割 Tarjan

BZOJ題目傳送門

洛谷題目傳送門

結論題。。。

跑一遍最小割，對殘量網絡進行縮點，使得剩下的邊都是滿流邊。

一條邊屬于最小割的并集當這條邊兩個端點所在的聯通塊不同。

一條邊屬于最小割的交集當這條邊兩個端點所在的聯通塊分别與源點和彙點相同。

下面給出口胡：

如果這條邊的兩個端點在同一個聯通塊内，那麼它就不是滿流邊，一定沒有割它流入的滿流邊劃算，也就不是最小割。

一條邊如果一個點屬于源點所在的聯通塊，它可以和一個點屬于彙點所在的聯通塊這樣的邊互相代替。

①将每個SCC縮成一個點，得到的新圖就隻含有滿流邊了。那麼新圖的任一s-t割都對應原圖的某個最小割，從中任取一個把id[u]和id[v]割開的割即可證明。

② 假設将(u,v)的邊權增大，那麼殘餘網絡中會出現s->u->v->t的通路，進而能繼續增廣，于是最大流流量（也就是最小割容量）會增大。這即說明(u,v)是最小割集中必須出現的邊。

​ —hzwer

最後統計答案的時候後向弧不能算。

代碼：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 4005
#define M 60005
#define F inline
using namespace std;
struct edge{ int nxt,to,v,x,f; }ed[M<<1];
int n,m,k=1,ti,s,t,tp,p,h[N],tmp[N],f[N],d[N],q[N];
int stk[N],dfn[N],low[N],num[N];
F char readc(){
	static char buf[100000],*l=buf,*r=buf;
	if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
	return l==r?EOF:*l++;
}
F int _read(){
	int x=0; char ch=readc();
	while (!isdigit(ch)) ch=readc();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
	return x;
}
F void add(int x,int y,int z){
	ed[++k]=(edge){h[x],y,z,x},h[x]=k;
	ed[++k]=(edge){h[y],x,0,y},h[y]=k;
}
F bool bfs(){
	int l=0,r=1; q[1]=s,d[s]=0,f[s]=++ti;
	while (l<r){
		int x=q[++l];
		for (int i=h[x],v;i;i=ed[i].nxt)
			if (ed[i].v>ed[i].f&&f[v=ed[i].to]!=ti)
				d[v]=d[x]+1,q[++r]=v,f[v]=ti;
	}
	return f[t]==ti;
}
int dfs(int x,int rem){
	if (x==t||!rem) return rem; int sum=0;
	for (int &i=tmp[x];i;i=ed[i].nxt)
		if (d[ed[i].to]==d[x]+1){
			int p=dfs(ed[i].to,min(rem,ed[i].v-ed[i].f));
			if (p) sum+=p,ed[i].f+=p,ed[i^1].f-=p,rem-=p;
			if (!rem) break;
		}
	return sum;
}
void Tarjan(int x){
	dfn[x]=low[x]=++p,stk[++tp]=x,f[x]=1;
	for (int i=h[x],v;i;i=ed[i].nxt)
		if (ed[i].v>ed[i].f)
			if (!dfn[v=ed[i].to]) Tarjan(v),low[x]=min(low[x],low[v]);
			else if (f[v]) low[x]=min(low[x],dfn[v]);
	if (dfn[x]==low[x]){
		while (stk[tp]!=x) num[stk[tp]]=x,f[stk[tp--]]=0;
		num[x]=x,f[x]=0,tp--;
	}
}
int main(){
	n=_read(),m=_read(),s=_read(),t=_read();
	for (int i=1,x,y,z;i<=m;i++)
		x=_read(),y=_read(),z=_read(),add(x,y,z);
	while (bfs()){ for (int i=1;i<=n;i++) tmp[i]=h[i]; dfs(s,1e9); }
	for (int i=1;i<=n;i++) f[i]=0;
	for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
	for (int i=1,x,v;i<=m;i++){
		if (ed[i<<1].f<ed[i<<1].v){ puts("0 0"); continue; }
		putchar(num[v=ed[i<<1].to]!=num[x=ed[i<<1].x]?'1':'0');
		puts(num[x]==num[s]&&num[v]==num[t]?" 1":" 0");
	}
	return 0;
}