网络流求最小割点，每个点分裂为入点和出点，边权为1
注：S，T分裂为边权为INF的两个点
出点到其它入点边权为INF
// ShellDawn// POJ1815// No.26#include<stdio.h>#include<string.h>#include<algorithm>#include<queue>#define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3fusing namespace std;#define maxn 205int N,S,T;int G[maxn][maxn];struct Edge{int to;int v;int rvs;int pre;};Edge E[maxn*maxn*4];int pre[maxn*2];int cnt = 1;int V[maxn*2];void addE(int from,int to,int v,int rvs){E[cnt].to = to;E[cnt].v = v;E[cnt].rvs = rvs;E[cnt].pre = pre[from];pre[from] = cnt++;}void build(){MM(pre,0);cnt = 1;for(int i=1;i<=N;i++){if(G[i][i] > 0){if(i == S || i == T){int t = cnt;addE(i,i+N,INF,t+1);addE(i+N,i,0,t);}else{int t = cnt;addE(i,i+N,1,t+1);addE(i+N,i,0,t);}}}for(int i=1;i<=N;i++){if(G[i][i] == 0) continue;for(int j=1;j<=N;j++){if( i == j || G[i][j] == 0 || G[j][j] == 0) continue;int t = cnt;addE(i+N,j,INF,t+1);addE(j,i+N,0,t);}}}void printE(){for(int i=1;i<=N*2;i++){printf("ID:%d ",i);for(int j=pre[i];j!=0;j=E[j].pre){printf("->%d (%d) ",E[j].to,E[j].v);}puts("");}}bool BFS(int s){MM(V,0);V[s] = 1;queue<int> q;q.push(s);while(!q.empty()){int now = q.front();q.pop();for(int i=pre[now];i!=0;i=E[i].pre){if(E[i].v > 0 && V[E[i].to] == 0){V[E[i].to] = V[now] + 1;q.push(E[i].to);}}}if(V[T+N] > 0) return true;return false;}int DFS(int now,int minflow){if(now == T+N) return minflow;int flow = 0;for(int i=pre[now]; i!=0 && minflow ; i=E[i].pre){if(E[i].v > 0 && V[E[i].to] == V[now] + 1){int f = DFS(E[i].to,min(minflow,E[i].v));flow += f;minflow -= f;E[i].v -= f;E[E[i].rvs].v += f;}}if(flow == 0) V[now] = 0;return flow;}int main(){//freopen("A.txt","r",stdin);scanf("%d%d%d",&N,&S,&T);for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){scanf("%d",&G[i][j]);}}if(G[S][T] > 0){puts("NO ANSWER!");return 0;}build();//printE();int maxflow = 0;while(BFS(S)) maxflow += DFS(S,INF);printf("%d\n",maxflow);queue<int> q;for(int i=1;i<=N && maxflow;i++){if(i == S || i == T) continue;G[i][i] = 0;build();int flow = 0;while(BFS(S)) flow+=DFS(S,INF);if(flow < maxflow){q.push(i);maxflow -- ;}else G[i][i] = 1;}while(!q.empty()){printf("%d",q.front());q.pop();if(q.empty()) puts("");else printf(" ");}return 0;}
