结论题，最小割，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";
    }
}

算法！美不胜收！