No.26 - POJ1815 最小割点

网络流求最小割点，每个点分裂为入点和出点，边权为1

注：S，T分裂为边权为INF的两个点
出点到其它入点边权为INF

// ShellDawn
// POJ1815
// No.26#include
#include
#include
#include
#define MM(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;#define maxn 205
int 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 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 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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！