求字典序最小的最小割，首先，对于每一个不是源点和汇点，拆成两个点，有一条容量为一的边。
求一次最小割后，针对每一个结点，按照字典序枚举若是删了它与它映射过去的另一个点之间的边是否会使得最小割变小，是则必须删它，否则，不用。
本来应该dfs求出S,T集合的来降低复杂度的（判断删去一条边是否会使得最小割变小），但是这道题点数边数都很小，直接暴力就行了。
View Code 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=500,M=10000; 6 const int inf=10000000; 7 int head[N],nc; 8 struct Edge 9 { 10 int x,y,next,cap; 11 } edge[M*4],sav[M*4]; 12 void add(int x,int y,int cap) 13 { 14 edge[nc].x=x; 15 edge[nc].y=y; 16 edge[nc].cap=cap; 17 edge[nc].next=head[x]; 18 head[x]=nc++; 19 edge[nc].x=y; 20 edge[nc].y=x; 21 edge[nc].cap=0; 22 edge[nc].next=head[y]; 23 head[y]=nc++; 24 } 25 int num[N],h[N],S,T,n,nn,m; 26 int findpath(int x,int flow) 27 { 28 if(x==T) 29 return flow; 30 int res=flow,pos=n-1; 31 for(int i=head[x]; i!=-1; i=edge[i].next) 32 { 33 int y=edge[i].y; 34 if(h[x]==h[y]+1&&edge[i].cap>0) 35 { 36 int tp=findpath(y,min(edge[i].cap,res)); 37 res-=tp; 38 edge[i].cap-=tp; 39 edge[i^1].cap+=tp; 40 if(!res||h[S]==n) 41 return flow-res; 42 } 43 if(edge[i].cap>0&&h[y]<pos) 44 pos=h[y]; 45 } 46 if(res==flow) 47 { 48 num[h[x]]--; 49 if(num[h[x]]==0) 50 { 51 h[S]=n; 52 return flow-res; 53 } 54 h[x]=pos+1; 55 num[h[x]]++; 56 } 57 return flow-res; 58 } 59 int Sap() 60 { 61 memset(h,0,sizeof(h)); 62 memset(num,0,sizeof(num)); 63 int ans=0; 64 num[0]=n; 65 while(h[S]!=n) 66 ans+=findpath(S,inf); 67 return ans; 68 } 69 int g[205][205]; 70 void rdfs(int x) 71 { 72 for(int i=head[x];i!=-1;i=edge[i].next) 73 { 74 if((i&1)&&(edge[i].cap)) 75 { 76 edge[i].cap--; 77 edge[i^1].cap++; 78 rdfs(edge[i].y); 79 } 80 } 81 } 82 void dfs(int x) 83 { 84 for(int i=head[x];i!=-1;i=edge[i].next) 85 { 86 if((!(i&1))) 87 { 88 if(edge[i].y==x+nn&&edge[i].cap==0) 89 { 90 edge[i].cap++; 91 edge[i^1].cap--; 92 dfs(edge[i].y); 93 } 94 else if(edge[i].cap<inf) 95 { 96 edge[i].cap++; 97 edge[i^1].cap--; 98 dfs(edge[i].y); 99 } 100 } 101 } 102 } 103 int main() 104 { 105 while(scanf("%d%d%d",&n,&S,&T)!=EOF) 106 { 107 bool flag=false; 108 for(int i=1;i<=n;i++) 109 { 110 for(int j=1;j<=n;j++) 111 { 112 scanf("%d",&g[i][j]); 113 if(g[i][j]&&i==S&&j==T) 114 flag=true; 115 } 116 } 117 if(flag) 118 { 119 printf("NO ANSWER!\n"); 120 continue; 121 } 122 memset(head,-1,sizeof(head)); 123 nc=0; 124 for(int i=1;i<=n;i++) 125 { 126 if(i!=S&&i!=T) 127 add(i,i+n,1); 128 for(int j=1;j<=n;j++) 129 { 130 if(g[i][j]&&i!=j) 131 { 132 if(i==S) 133 add(i,j,inf); 134 else if(i!=T) 135 add(i+n,j,inf); 136 } 137 } 138 } 139 memcpy(sav,edge,sizeof(Edge)*nc); 140 nn=n; 141 n=n*2-2; 142 int ans=Sap(); 143 printf("%d\n",ans); 144 for(int i=1;i<=nn;i++) 145 { 146 if(i!=S&&i!=T) 147 for(int j=head[i];j!=-1;j=edge[j].next) 148 { 149 if(edge[j].cap==0&&edge[j].y==i+nn) 150 { 151 sav[j].cap=sav[j^1].cap=0; 152 memcpy(edge,sav,sizeof(Edge)*nc); 153 if(Sap()!=ans-1) 154 { 155 sav[j].cap=1; 156 sav[j^1].cap=0; 157 continue; 158 } 159 if(flag) 160 printf(" "); 161 else 162 flag=true; 163 printf("%d",i); 164 ans--; 165 break; 166 } 167 } 168 } 169 printf("\n"); 170 } 171 return 0; 172 }
