題目

A,B兩個國家正在交戰，其中A國的物資運輸網中有N個中轉站，M條單向道路。設其中第i (1≤i≤M)條道路連接了vi,ui兩個中轉站，那么中轉站vi可以通過該道路到達ui中轉站，如果切斷這條道路，需要代價ci。現在B國想找出一個路徑切斷方案，使中轉站s不能到達中轉站t，并且切斷路徑的代價之和最小。 小可可一眼就看出，這是一個求最小割的問題。但愛思考的小可可并不局限于此。現在他對每條單向道路提出兩個問題： 問題一：是否存在一個最小代價路徑切斷方案，其中該道路被切斷？ 問題二：是否對任何一個最小代價路徑切斷方案，都有該道路被切斷？ 現在請你回答這兩個問題。

輸入格式

第一行有4個正整數，依次為N,M,s和t。第2行到第(M+1)行每行3個正 整數v,u,c表示v中轉站到u中轉站之間有單向道路相連，單向道路的起點是v， 終點是u,切斷它的代價是c(1≤c≤100000)。 注意:兩個中轉站之間可能有多條道路直接相連。 同一行相鄰兩數之間可能有一個或多個空格。

輸出格式

對每條單向邊，按輸入順序，依次輸出一行，包含兩個非0即1的整數，分 別表示對問題一和問題二的回答(其中輸出1表示是，輸出0表示否)。 同一行相鄰兩數之間用一個空格隔開，每行開頭和末尾沒有多余空格。

輸入樣例

6 7 1 6

1 2 3

1 3 2

2 4 4

2 5 1

3 5 5

4 6 2

5 6 3

輸出樣例

1 0

1 0

0 0

1 0

0 0

1 0

1 0

提示

設第(i+1)行輸入的邊為i號邊，那么{1,2},{6,7},{2,4,6}是僅有的三個最小代價切割方案。它們的并是{1,2,4,6,7}，交是 。 【數據規模和約定】 測試數據規模如下表所示 數據編號 N M 數據編號 N M 1 10 50 6 1000 20000 2 20 200 7 1000 40000 3 200 2000 8 2000 50000 4 200 2000 9 3000 60000 5 1000 20000 10 4000 60000

2015.4.16新加數據一組，可能會卡掉從前可以過的程序。

題解

先跑最大流求出任意一個最小割

對殘量網絡縮點

然后對于一條滿流的邊(u,v)

①Scc[u]!=Scc[v]，存在(u,v)被割的方案

②Scc[u]Scc[S]&&Scc[v]Scc[T]，(u,v)必定被割

jcvb:

在殘余網絡上跑tarjan求出所有SCC，記id[u]為點u所在SCC的編號。顯然有id[s]!=id[t]（否則s到t有通路，能繼續增廣）。

①對于任意一條滿流邊(u,v)，(u,v)能夠出現在某個最小割集中，當且僅當id[u]!=id[v]；

②對于任意一條滿流邊(u,v)，(u,v)必定出現在最小割集中，當且僅當id[u]id[s]且id[v]id[t]。

①

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

②

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

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 4005,maxm = 200005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}

	return out * flag;

}

int h[maxn],ne = 2,n,m,S,T;

struct EDGE{int from,to,nxt,f;}ed[maxm];

inline void build(int u,int v,int w){

	ed[ne] = (EDGE){u,v,h[u],w}; h[u] = ne++;

	ed[ne] = (EDGE){v,u,h[v],0}; h[v] = ne++;

}

int vis[maxn],d[maxn],cur[maxn];

bool bfs(){

	memset(d,0,sizeof(d));

	memset(vis,0,sizeof(vis));

	queue<int> q;

	vis[S] = true; q.push(S); int u;

	while (!q.empty()){

		u = q.front(); q.pop();

		Redge(u) if (ed[k].f && !vis[to = ed[k].to]){

			d[to] = d[u] + 1; vis[to] = true; q.push(to);

		}

	}

	return vis[T];

}

int dfs(int u,int minf){

	if (u == T || !minf) return minf;

	int f,flow = 0,to;

	if (cur[u] == -1) cur[u] = h[u];

	for (int& k = cur[u]; k; k = ed[k].nxt)

		if (d[to = ed[k].to] == d[u] + 1 && (f = dfs(to,min(ed[k].f,minf)))){

			ed[k].f -= f; ed[k ^ 1].f += f;

			flow += f; minf -= f;

			if (!minf) break;

		}

	return flow;

}

int maxflow(){

	int flow = 0;

	while (bfs()){

		for (int i = 1; i <= n; i++) cur[i] = -1;

		flow += dfs(S,INF);

	}

	return flow;

}

int dfn[maxn],low[maxn],st[maxn],Scc[maxn],top,cnt,scci;

void dfs(int u){

	dfn[u] = low[u] = ++cnt;

	st[++top] = u;

	Redge(u) if (ed[k].f){

		if (!dfn[to = ed[k].to]){

			dfs(to);

			low[u] = min(low[u],low[to]);

		}else if (!Scc[to]) low[u] = min(low[u],dfn[to]);

	}

	if (dfn[u] == low[u]){

		scci++;

		do{

			Scc[st[top]] = scci;

		}while (st[top--] != u);

	}

}

int ans[2][maxm];

int main(){

	n = read(); m = read(); S = read(); T = read(); int a,b,w;

	REP(i,m){

		a = read(); b = read(); w = read();

		build(a,b,w);

	}

	maxflow();

	REP(i,n) if (!dfn[i]) dfs(i);

	for (int i = 1; i <= m; i++){

		int k = i << 1;

		if (!ed[k].f){

			if (Scc[ed[k].from] != Scc[ed[k].to]) ans[0][i] = 1;

			if (Scc[ed[k].from] == Scc[S] && Scc[ed[k].to] == Scc[T]) ans[1][i] = 1;

		}

	}

	for (int i = 1; i <= m; i++) printf("%d %d\n",ans[0][i],ans[1][i]);

	return 0;

}

總結

以上是生活随笔為你收集整理的BZOJ1797 [Ahoi2009]Mincut 最小割 【最小割唯一性判定】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。