1797: [Ahoi2009]Mincut 最小割
分析：
题意为：问一条边是否可能存在于最小割中，是否一定存在于最小割中。
首先最小割的边一定是满流的边。且这条边点两个端点u.v中，至少一个与S或T联通。而且在残量网络中u->v没有增广路。如果存在增广路，那么会使最小割的增加。这条增广路会和u->v的反向边构成强连通分量。所以一条边可能存在于最小割中，要满足：满流， 残量网络中u,v不属于一个强连通分量。
那么第二问就是要求S一定可以到u，v一定可以到T。此时如果存在这样的一条路径，会和S->u的反向边构成强连通分量，于是一条边一定存在于最小割中，满足：满流，残量网络中S和u属于同一个强连通分量，v和T属于同一个强连通分量。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = , INF = 1e9;
struct Edge { int fr, to, nxt, cap; } e[];
int head[N], cur[N], dis[N], q[N], low[N], dfn[N], sk[N], bel[N];
int Index, top, S, T, En = , n, m, cnt;
bool vis[N]; inline void add_edge(int u,int v,int w) {
++En; e[En].fr = u, e[En].to = v, e[En].cap = w, e[En].nxt = head[u]; head[u] = En;
++En; e[En].fr = v, e[En].to = u, e[En].cap = , e[En].nxt = head[v]; head[v] = En;
}
bool bfs() {
for (int i = ; i <= n; ++i) cur[i] = head[i], dis[i] = -;
int L = , R = ;
q[++R] = S; dis[S] = ;
while (L <= R) {
int u = q[L ++];
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] == - && e[i].cap > ) {
dis[v] = dis[u] + ; q[++R] = v;
if (v == T) return true;
}
}
}
return false;
}
int dfs(int u,int flow) {
if (u == T) return flow;
int used = , tmp;
for (int &i = cur[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (dis[v] == dis[u] + && e[i].cap > ) {
tmp = dfs(v, min(flow - used, e[i].cap));
if (tmp > ) {
used += tmp; e[i].cap -= tmp; e[i ^ ].cap += tmp;
if (used == flow) break;
}
}
}
if (used != flow) dis[u] = -;
return used;
}
int dinic() {
int ans = ;
while (bfs()) ans += dfs(S, INF);
return ans;
}
void tarjan(int u) {
low[u] = dfn[u] = ++Index;
sk[++top] = u, vis[u] = ;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (e[i].cap) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
++cnt;
do {
bel[sk[top]] = cnt;
vis[sk[top]] = false;
top --;
} while (sk[top + ] != u);
}
}
int main() {
n = read(), m = read(); S = read(), T = read();
for (int i = ; i <= m; ++i) {
int u = read(), v = read(), w = read();
add_edge(u, v, w);
}
dinic();
for (int i = ; i <= n; ++i)
if (!dfn[i]) tarjan(i);
for (int i = ; i <= En; i += ) {
if (e[i].cap > ) puts("0 0");
else {
printf(bel[e[i].fr] != bel[e[i].to] ? "1 " : "0 ");
puts(bel[e[i].fr] == bel[S] && bel[e[i].to] == bel[T] ? "" : "");
}
}
return ;
}