poj 1815 Friendship

给出一张无向图（输入方式是有向图），给定源点和汇点，求最少割掉几个点使得源点与汇点不连通，并输出字典序最小的一组解。

由小到大枚举每个点（除了源点和汇点），删掉该点后跑最大流，若最大流减少则记录，不减少则将该点加回。直到记录点数达到答案，即得到字典序最小的一组解。

  1 #include<cstring>
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 const int dian=405;
  8 const int bian=100005;
  9 const int INF=0x3f3f3f3f;
 10 const int inf=10000;
 11 int h[dian],nxt[bian],ver[bian],val[bian],ch[dian],cr[dian];
 12 int n,tot,aa,ans;
 13 int S,T;
 14 void add(int a,int b,int c){
 15     tot++;ver[tot]=b;val[tot]=c;nxt[tot]=h[a];h[a]=tot;
 16     tot++;ver[tot]=a;val[tot]=0;nxt[tot]=h[b];h[b]=tot;
 17 }
 18 bool tell(){
 19     memset(ch,-1,sizeof(ch));
 20     queue<int>q;
 21     q.push(S);
 22     ch[S]=0;
 23     while(!q.empty()){
 24         int t=q.front();
 25         q.pop();
 26         for(int i=h[t];i;i=nxt[i])
 27             if(ch[ver[i]]==-1&&val[i]){
 28                 ch[ver[i]]=ch[t]+1;
 29                 q.push(ver[i]);
 30             }
 31     }
 32     return ch[T]!=-1;
 33 }
 34 int zeng(int a,int b){
 35     if(a==T)
 36         return b;
 37     int r=0;
 38     for(int i=cr[a];i&&b>r;i=nxt[i])
 39         if(ch[ver[i]]==ch[a]+1&&val[i]){
 40             int t=zeng(ver[i],min(val[i],b-r));
 41             val[i]-=t,r+=t,val[i^1]+=t;
 42             if(val[i])
 43                 cr[a]=i;
 44         }
 45     if(!r)
 46         ch[a]=-1;
 47     return r;
 48 }
 49 int dinic(){
 50     int r=0,t;
 51     while(tell()){
 52         for(int i=1;i<=n+n;i++)
 53             cr[i]=h[i];
 54         while(t=zeng(S,INF))
 55             r+=t;
 56     }
 57     return r;
 58 }
 59 int main(){
 60     memset(h,0,sizeof(h));
 61     memset(nxt,0,sizeof(nxt));
 62     tot=1;
 63     scanf("%d%d%d",&n,&S,&T);
 64     S+=n;
 65     for(int i=1;i<=n;i++)
 66         add(i,i+n,1);
 67     for(int i=1;i<=n;i++)
 68         for(int j=1;j<=n;j++){
 69             scanf("%d",&aa);
 70             if(aa)
 71                 add(i+n,j,inf);
 72         }
 73     ans=dinic();
 74     for(int i=2;i<=tot;i+=2){
 75         val[i]+=val[i^1];
 76         val[i^1]=0;
 77     }
 78     if(ans>=10000){
 79         printf("NO ANSWER!");
 80         return 0;
 81     }
 82     printf("%d
",ans);
 83     for(int i=1;i<=n;i++){
 84         if(!ans)
 85             break;
 86         if(i==S||i==T)
 87             continue;
 88         val[2*i]=0;
 89         if(dinic()<ans){
 90             printf("%d ",i);
 91             ans--;
 92         }
 93         else
 94             val[2*i]=1;
 95         for(int j=2;j<=tot;j+=2){
 96             val[j]+=val[j^1];
 97             val[j^1]=0;
 98         }
 99     }
100     return 0;
101 }

据说有一遍dinic加一遍floyd的优秀做法，本人太弱决定放弃。