poj1815最小割

题解给的拆点法，mp[i][i+n]=1;  求按字典序的最小割集的时候很巧的是枚举去点的时候，去的是一个饱和流的边，这个很巧啊。  最小割的 割集一定是饱和边，但是饱和边不一定是属于最小割割集。他这样去点的时候如果最小割的值减小了就把他输出保证了字典序。因为这个点点之间的值为1，所以如果最小割减小了这个肯定是最小割集中一条边。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;

const int maxn=222*2;
int level[maxn];
int Map[maxn][maxn];
int n,s,e;
int Map1[maxn][maxn];
const int INF=0xfffffff;
int Min(int a,int b)
{
    return a>b?b:a;
}

bool bfs()
{
    memset(level,0,sizeof(level));
    int l=0;int r=0;
    int q[maxn*2];
    q[r++]=s;level[s]=1;
    while(l<r){
        int cur=q[l++];
        if(cur==e) break;
        for(int i=1;i<=2*n;i++){
            if(Map1[cur][i]-Map[cur][i]&&!level[i]) {
                q[r++]=i;
                level[i]=level[cur]+1;
            }
        }
    }
    return level[e];
}

int dfs(int x,int val)
{
    if(x==e) return val;
    int sum=0;
    for(int i=1;i<=2*n&&val;i++){
        if(Map1[x][i]-Map[x][i]&&level[i]==level[x]+1){
            int t=dfs(i,Min(val,Map1[x][i]-Map[x][i]));
            Map[x][i]+=t;Map[i][x]-=t;
            sum+=t;val-=t;
        }
    }
    if(sum==0) level[x]=-1;
    return sum;
}

int dinic()
{
    int ans=0;int t;
    while(bfs()){
        while(t=dfs(s,INF)) ans+=t;
    }
    return ans;
}

void solve()
{
    int ans=dinic();
    if(Map1[s+n][e-n]){
        printf("NO ANSWER!
");
        return ;
    }
    printf("%d
",ans);
    if(ans){
    for(int i=1;i<=n;i++){
        if(i==s||i==e-n) continue;
        memset(Map,0,sizeof(Map));
        Map1[i][i+n]=0;
        int ans1=dinic();
        if(ans1<ans){
            ans=ans1;
            printf("%d ",i);
        }
        else Map1[i][i+n]=1;
        if(ans==0) break;
    }
    printf("
");
    }
}
int main()
{
    int t;
    while(~scanf("%d%d%d",&n,&s,&t)){
    memset(Map1,0,sizeof(Map1));
    for(int i=1;i<=n;i++)
    Map1[i][i+n]=1;
    Map1[s][s+n]=INF;
    Map1[t][t+n]=INF;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        int gg;
        scanf("%d",&gg);
        if(gg&&i!=j)
            Map1[i+n][j]=INF;
    }
    e=t+n;
    solve();
    }
    return 0;
}