Sabotage

这里学到的是一个输出最小割的方案！！！
在跑完最大流后，属于最小割的边肯定cap都为零了。
我们再以源点为起点进行dfs搜索，标记。
然后最小割会将其阻拦住，然后我们再遍历边，看有哪些边一端被标记了另一端没有被标记。
这样就好了。

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int> pii;
const int max_n = 100;
const int max_m = 1000;
const int inf = 2e9;
struct edge {
    int to,cap,next;
}E[max_m<<2];
int n,m;
int head[max_n],cnt=1,gap[max_n],last[max_n],d[max_n],que[max_n],ql,qr;
void add(int u,int to,int cap) {
    E[++cnt].to=to;E[cnt].cap=cap;
    E[cnt].next=head[u];head[u]=cnt;
    E[++cnt].to=u;E[cnt].cap=0;
    E[cnt].next=head[to];head[to]=cnt;
}int aug(int x,int s,int t,int mi) {
    if (x==t) return mi;
    int flow=0;
    for (int &i=last[x],v=E[i].to;i;i=E[i].next,v=E[i].to) if (d[x]==d[v]+1) {
        int tmp=aug(v,s,t,min(mi,E[i].cap));
        flow+=tmp,mi-=tmp,E[i].cap-=tmp,E[i^1].cap+=tmp;
        if (!mi) return flow;
    }
    if (!(--gap[d[x]])) d[s]=n+1;
    ++gap[++d[x]],last[x]=head[x];
    return flow;
}
int maxflow(int s,int t) {
    fill(gap,gap+n+10,0);fill(d,d+n+10,0);
    ++gap[d[t]=1];
    for (int i=1;i<=n;++i) last[i]=head[i];
    que[ql=qr=1]=t;
    while (ql<=qr) {
        int x=que[ql++];
        for (int i=head[x],v=E[i].to;i;i=E[i].next,v=E[i].to) if (!d[v]) ++gap[d[v]=d[x]+1],que[++qr]=v;
    }

    int ret=aug(s,s,t,inf);
    while (d[s]<=n)    ret+=aug(s,s,t,inf);
    return ret;
}
int vis[100];
void dfs(int u){
    vis[u]=1;
    for (int i=head[u];i;i=E[i].next){
        if (E[i].cap==0)continue;
        if (vis[E[i].to])continue;
        dfs(E[i].to);
    }
}
int main(){
    while(scanf("%d %d",&n,&m)){
        if (n==m&&n==0)break;
        fill(head,head+n+5,0);cnt=1;
        for (int i=1,u,v,c;i<=m;++i){
            scanf("%d %d %d",&u,&v,&c);
            add(u,v,c);add(v,u,c);
        }
        maxflow(1,2);
        set<pii> res;
        fill(vis,vis+max_n,0);
        dfs(1);
        for (int u=1;u<=n;++u){
            for (int i=head[u];i;i=E[i].next){
                if (i&1)continue;
                if (E[i].cap==0&&(vis[E[i].to]^vis[u]))
                    res.insert(pii(min(u,E[i].to),max(u,E[i].to)));
            }
        }
        for (auto it=res.begin();it!=res.end();++it)
            printf("%d %d\n",(*it).first,(*it).second);
        printf("\n");
    }
}