![BZOJ 1797: [Ahoi2009]Mincut 最小割( 网络流 )](/default/index/img?u=aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmFXMWhaMlZ6TWpBeE5TNWpibUpzYjJkekxtTnZiUzlpYkc5bkx6Y3lNemc1Tmk4eU1ERTFNRGt2TnpJek9EazJMVEl3TVRVd09UQTFNVEl6TVRBeU56WTBMVEV4TmprM09UazJNQzV3Ym1jPS5qcGc= "BZOJ 1797: [Ahoi2009]Mincut 最小割( 网络流 )")
先跑网络流, 然后在残余网络tarjan缩点.
考虑一条边(u,v):
当且仅当scc[u] != scc[v], (u,v)可能出现在最小割中...然而我并不会证明
当且仅当scc[u] = scc[S] && scc[v] == scc[T], (u, v) 必定出现在最小割中. 这个很好脑补, 假如这条边不是满流, 那么S-T就存在增广路了..
------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 4009;
const int maxm = 60009;
const int INF = 10000000;
struct edge {
int to, id, cap;
edge *next, *rev;
} E[maxm << 1], *head[maxn], *pt = E;
inline void add(int u, int v, int w, int id) {
pt->to = v; pt->cap = w; pt->id = id;
pt->next = head[u]; head[u] = pt++;
}
inline void addedge(int u, int v, int w, int id) {
add(u, v, w, id); add(v, u, 0, -1);
head[u]->rev = head[v];
head[v]->rev = head[u];
}
edge *p[maxn], *cur[maxn];
int h[maxn], cnt[maxn], ans[maxm][2], N, S, T;
stack<int> sta;
int dfn[maxn], low[maxn], scc[maxn], CK = 0, n = 0;
void maxFlow() {
memset(h, 0, sizeof h);
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < N; i++) cur[i] = head[i];
cnt[0] = N;
edge* e;
for(int x = S, A = INF; h[S] < N; ) {
for(e = cur[x]; e; e = e->next)
if(e->cap && h[e->to] + 1 == h[x]) break;
if(e) {
A = min(A, e->cap);
p[e->to] = cur[x] = e;
x = e->to;
if(x == T) {
for(; x != S; x = p[x]->rev->to) {
p[x]->cap -= A;
p[x]->rev->cap += A;
}
A = INF;
x = S;
}
} else {
if(!--cnt[h[x]]) break;
h[x] = N;
for(e = head[x]; e; e = e->next) if(h[e->to] + 1 < h[x] && e->cap) {
h[x] = h[e->to] + 1;
cur[x] = e;
}
++cnt[h[x]];
if(x != S) x = p[x]->rev->to;
}
}
}
void tarjan(int x) {
dfn[x] = low[x] = CK++;
sta.push(x);
for(edge* e = head[x]; e; e = e->next) if(e->cap) {
if(!~dfn[e->to])
tarjan(e->to), low[x] = min(low[x], low[e->to]);
else if(!~scc[e->to])
low[x] = min(low[x], dfn[e->to]);
}
if(dfn[x] == low[x]) {
int t;
do {
t = sta.top(); sta.pop();
scc[t] = n;
} while(t != x);
n++;
}
}
int main() {
int m;
scanf("%d%d%d%d", &N, &m, &S, &T); S--; T--;
for(int i = 0; i < m; i++) {
int u, v, c; scanf("%d%d%d", &u, &v, &c); u--; v--;
addedge(u, v, c, i);
}
maxFlow();
memset(dfn, -1, sizeof dfn);
memset(low, -1, sizeof low);
memset(scc, -1, sizeof scc);
for(int i = 0; i < N; i++) if(!~dfn[i]) tarjan(i);
for(int i = 0; i < N; i++)
for(edge* e = head[i]; e; e = e->next) if(~e->id && !e->cap) {
if(scc[i] != scc[e->to]) ans[e->id][0] = 1;
if(scc[i] == scc[S] && scc[e->to] == scc[T]) ans[e->id][1] = 1;
}
for(int i = 0; i < m; i++)
printf("%d %d\n", ans[i][0], ans[i][1]);
return 0;
}
------------------------------------------------------------------------------------
1797: [Ahoi2009]Mincut 最小割
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1476 Solved: 624
[Submit][Status][Discuss]
Description
A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题： 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？ 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？ 现在请你回答这两个问题。
Input
第一行有4个正整数，依次为N,M,s和t。第2行到第(M+1)行每行3个正 整数v,u,c表示v中转站到u中转站之间有单向道路相连，单向道路的起点是v， 终点是u,切断它的代价是c(1≤c≤100000)。 注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。
Output
对每条单向边，按输入顺序，依次输出一行，包含两个非0即1的整数，分 别表示对问题一和问题二的回答(其中输出1表示是，输出0表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
Sample Input
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
Sample Output
1 0
1 0
0 0
1 0
0 0
1 0
1 0
HINT
设第(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新加数据一组，可能会卡掉从前可以过的程序。
Source