poj1815 无向图 拆点的最小割
转载来自：https://www.cnblogs.com/xingxing1024/p/5244676.html
题目来源：http://poj.org/problem?id=1815
n<=200
这个题的意思是给你一个无向图， 其中有两个点S, T, 让你去掉图中最小数量的点使得S无法到达T， 不能去掉S或者T, 我们将一个顶点i拆成两个点2*i-1 -> 2*i, 边权为1， 对于一条边i - j, 那么就有2*i -> 2*j-1, 2*j -> 2*i-1, 边权为inf， 然后就是枚举边来求解最小割了， 代码如下：
拆点后，跑一遍最大流，然后枚举边输出路径，这个输出路径很暴力，不过n比较小，可以这样搞。先放上代码，以后补。。。
#include
#include
#include
#include
#include using namespace std;
const int inf = 0x3fffffff;
const int maxn = 200*2+100;struct Dinic
{int n; //n个顶点struct edge{int from, to, cap;};vector G[maxn];vector e;int level[maxn], iter[maxn];void init(){for(int i=0; i<=n; i++) G[i].clear();e.clear();}void add_edge(int u, int v, int cap){e.push_back((edge){u, v, cap});e.push_back((edge){v, u, 0});int m = e.size();G[u].push_back(m-2);G[v].push_back(m-1);}void bfs(int s){memset(level, -1, sizeof(level));queue que;level[s] = 0;que.push(s);while(!que.empty()){int u = que.front();que.pop();for(int i=0; i0 && level[te.to]<0){level[te.to] = level[u] + 1;que.push(te.to);}}}}int dfs(int v, int t, int f){if(v == t) return f;for(int &i=iter[v]; i0 && level[v] 0){tpe.cap -= d;e[G[v][i]^1].cap += d;return d;}}}return 0;}int max_flow(int s, int t){int flow = 0;for(;;){bfs(s);if(level[t]<0) return flow;memset(iter, 0, sizeof(iter));int f;while((f=dfs(s, t, 0x3fffffff)) > 0)flow += f;}}
} di1, di2;
int N, S, T;int main()
{scanf("%d%d%d", &N, &S, &T);di1.n = 2*N;di1.init();for(int i=1; i<=N; i++)di1.add_edge(2*i-1, 2*i, 1);bool flog = true;for(int i=1; i<=N&&flog; i++)for(int j=1; j<=N&&flog; j++){int t;scanf("%d", &t);if(j>i && t==1){//i -> jdi1.add_edge(2*i, 2*j-1, inf);di1.add_edge(2*j, 2*i-1, inf);if((i==S&&j==T)||(j==S&&i==T)) flog=false;}}if(!flog){printf("NO ANSWER!\n");return 0;}vector ans;di2 = di1;int f = di2.max_flow(2*S, 2*T-1);for(int i=0; i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！