结论题，最小割，tarjan
题意：
分析：
题目看了，就是让我们对图中的每一条边都做判断：是否可以是最小割边？是否一定是最小割边？
暴力做法：n*m对于每一条边我们都单独判断！
那么现在来看tarjan做法：
首先让我们想想，传统如何判断一条边能不能在最小割集中。
先跑最大流，得到其残余网络(此残余网络中满流边自动断开，即cap==0我们就当他不存在)
1.对于边e(u,v)如果e没有满流，那么绝对不是最小割。
2.对于边e(u,v)如果满流但是在残余网络中有一路径使得u->v那么他绝对不是最小割。
3.对于边e(u,v)如果满流且残余网络中不存在u->v那么可以是最小割
4.对于边e(u,v)如果满流且残余网络中存在s->u和v->t那么其一定为是最小割
上面是结论，接下来我将一一为您证明：(个人理解证明，非专业)
最大流==最小割，这时大家都知道的。
那么我们进行割边的过程其实也就是阻断最大流的过程。
最大流:maxflow,最小割:maxflow
如果我们对于一条边e(u,v)进行割边我们最多阻断e.cap流量的流
这意味着，我们每割一条边都必须阻断e.cap流量的流。因为最小割和最大流是相等的！！！！消耗和收获一定相等
OK！基于这个判断让我们再看看之前的结论：
1.对于边e(u,v)如果e没有满流，那么绝对不是最小割。
没有满流，假设e.cap = 10,e,flow = 7 那么我们对其进行切割也不过是阻断了7单位的流量。没用！！所以，不是最小割！
2.对于边e(u,v)如果满流但是在残余网络中有一路径使得u->v那么他绝对不是最小割。
假设e(u,v) e.flow == e.cap 但是在参与网络中还有路径(即未满流的边)使得u->v假设这条路径能穿流 f
那么我们切割e，也只能阻断e.cap-f的单位的流，消耗e.cap。所以不可能！！！
3.对于边e(u,v)如果满流且残余网络中不存在u->v那么可以是最小割
参考上面两条，我们知道此时消耗与收获相同，此边可以为最小割
4.对于边e(u,v)如果满流且残余网络中存在s->u和v->t那么其一定为是最小割
证明着一条定理，我们先来区分一下可以是最小割的边和一定是最小割的边的区别。
可以是最小割的边：
即我可以不割他，通过割其他的边以相同的代价来阻断最大流。
如图：
我们可以不切容量为5的边而切容量为2，和3的后面的边来阻断。
课时这种情况呢：
这能切容量为5的变了吧。
同理，这种情况呢：
前面的和后面的情况是相似的。
那么我们可以总结一下，其实就是：
对于边e(u,v)如果残余网络中存在s->u和v->t的路径那么我们是一定要切断这条边的！！！！得证
至此，四条定理全部得证。
——————————————————————分割线—————————————————————————————
1.对于边e(u,v)如果e没有满流，那么绝对不是最小割。
2.对于边e(u,v)如果满流但是在残余网络中有一路径使得u->v那么他绝对不是最小割。
3.对于边e(u,v)如果满流且残余网络中不存在u->v那么可以是最小割
4.对于边e(u,v)如果满流且残余网络中存在s->u和v->t那么其一定为是最小割
拿下来看的方便。。。。。。。。。
那么，第一条定理很好判断，跑一下最大流，看一下这条边的cap是否为0就好了。
但第二条，我们如何判断是否存在u->v呢？
如果我们是判断一条边就好了，直接dfs。但是判断所有条边显然不能这样。
关键
残余网络中是包含反向变的。因为e.cao==0 所以有一条v->u
那这时倘若有u->v，那么岂不是构成强连通了嘛！！
所以，我们只需对残余网络跑一遍tarjan。然后判断u和v是否在一个连通分量里面就好了！！
那么，同理对于第四结论。判断是否存在s->u和v->t。
肯定存在t->v 和 u->s!为什么？请看：
存在流量的路径 v->a1->a2->a3->....->t 那么一定存在其反向边 t->...->a3->a2->a1->v
同理u->s也一样。
因此同理若残余网络中存在s->u 和 v->t的话。
那么一定s与u，v与t一定是构成了强连通！！
判断s，u v，t是否在相同的强连通分量里面就好了！！！！！
总结一下，那四个结论就变为了
1.对于边e(u,v)如果e没有满流，那么绝对不是最小割。
2.对于边e(u,v)如果满流但是在残余网络中color[u]==color[v]那么他绝对不是最小割。
3.对于边e(u,v)如果满流且残余网络中color[u]!=color[v]那么可以是最小割
4.对于边e(u,v)如果满流且残余网络中color[s]==color[u]&&color[v]==color[t]那么其一定为是最小割
综上，此题得解!!!!!!!
苦思冥想，个人所得，并不严谨。如有错误，希望指出！！
代码如下：
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 4e3 + 100;
const int max_m = 1e6 + 100;
int n, m;int s, t;
int us[max_m], vs[max_m];
struct edge
{
int to, cap, rev, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;
void add(int from, int to,int cap) {
E[cnt].to = to;E[cnt].cap = cap;
E[cnt].rev = cnt + 1;
E[cnt].next = head[from];
head[from] = cnt++;
E[cnt].to = from;E[cnt].cap = 0;
E[cnt].rev = cnt - 1;
E[cnt].next = head[to];
head[to] = cnt++;
}
int iter[max_n];
int dist[max_n];
bool searchpath(int s, int t) {
fill(dist, dist + 1 + n, -1);
queue<int> que;dist[s] = 0;
que.push(s);
while (!que.empty()) {
int u = que.front();que.pop();
for (int i = head[u];i;i = E[i].next) {
edge& e = E[i];
if (dist[e.to] != -1 || e.cap == 0)continue;
dist[e.to] = dist[u] + 1;
que.push(e.to);
}
}return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
if (u == t)return f;
for (int& i = iter[u];i;i = E[i].next) {
edge& e = E[i];
if (dist[e.to] <= dist[u] || e.cap == 0)continue;
int d = matchpath(e.to, t, min(f, e.cap));
if (d <= 0)continue;
e.cap -= d;E[e.rev].cap += d;
return d;
}return false;
}
int dinic(int s,int t) {
int flow = 0;int f;
while (searchpath(s, t)) {
for (int i = 1;i <= n;i++)iter[i] = head[i];
while (f = matchpath(s, t, inf))
flow += f;
}return flow;
}
int dfn[max_n], low[max_n], color[max_n];
int tot = 0, colour = 0;
stack<int> st;
void tarjan(int u) {
dfn[u] = low[u] = tot++;st.push(u);
for (int i = head[u];i;i = E[i].next) {
edge& e = E[i];
if (!e.cap)continue;
if (!dfn[e.to]) { tarjan(e.to);low[u] = min(low[u], low[e.to]); }
else if (color[e.to] == 0)low[u] = min(low[u], dfn[e.to]);
}if (dfn[u] != low[u])return;
colour++;
while (st.top() != u) {
color[st.top()] = colour;
st.pop();
}color[st.top()] = colour;st.pop();
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m >> s >> t;
for (int i = 1;i <= m;i++) {
int cap;
cin >> us[i] >> vs[i] >> cap;
add(us[i], vs[i], cap);
}dinic(s, t);
for (int i = 1;i <= n;i++)
if (!dfn[i])tarjan(i);
for (int i = 1;i <= m;i++) {
edge& e = E[i * 2 - 1];
if (e.cap || color[us[i]] == color[vs[i]])
cout << "0 0\n";
else if (color[us[i]] == color[s] && color[vs[i]] == color[t])
cout << "1 1\n";
else
cout << "1 0\n";
}
}算法！美不胜收！
京公网安备 11010502036488号