首页 > 代码库 > POJ2125 Destroying The Graph 二分图 + 最小点权覆盖 + 最小割
POJ2125 Destroying The Graph 二分图 + 最小点权覆盖 + 最小割
思路来源：http://blog.csdn.net/lenleaves/article/details/7873441
求最小点权覆盖，同样求一个最小割，但是要求出割去了那些边，
只要用最终的剩余网络进行一次遍历就可以了，比较简单。
建图：同样是一个二分图，左边的点代表去掉出边，
右边的点代表去掉入边（小心别弄混），左边去掉出边的点与源点相连，
容量为wi- 。
然后更据给出的弧进行连线，权值为INF
使用很好理解的EK算法：（360MS）
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <climits>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define mm(a) memset((a),0,sizeof((a)))#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 220;queue <int> que;int vis[MAXN], res[MAXN], pre[MAXN];int n, m, map[MAXN][MAXN];int src, des;stack <int> ss;bool bfs(int src, int des){ int index; memset(pre, -1, sizeof(pre)); while(!que.empty()) que.pop(); pre[src] = 0; que.push(src); while(!que.empty()){ index = que.front(); que.pop(); for(int i = src; i <= des; ++i){ if(pre[i] == -1 && map[index][i] > 0){ pre[i] = index; if(i == des) return true; que.push(i); } } } return false;}int MaxFlow(int src, int des){ int i, maxflow = 0; while(bfs(src, des)){ int minflow = INF; for(i = des; i != src; i = pre[i]) minflow = min(minflow, map[pre[i]][i]); for(i = des; i != src; i = pre[i]){ map[pre[i]][i] -= minflow; map[i][pre[i]] += minflow; } maxflow += minflow; } return maxflow;}void init(){ mm(map);mm(vis);}void dfs(int p){ if(vis[p]) return ; vis[p] = true; for(int i = src; i < des; ++i) if(!vis[i] && map[p][i]) dfs(i);}void solve(){ int i, x, y, ans = 0, temp; init(); for(i = 1; i <= n; ++i) scanf("%d",&map[n + i][n * 2 + 1]); for(i = 1; i <= n; ++i) scanf("%d",&map[0][i]); for(i = 1; i <= m; ++i){ scanf("%d%d",&x,&y); map[x][y + n] = INF; } n = n << 1; src = 0, des = n + 1; ans = MaxFlow(src, des); dfs(0); printf("%d\n",ans); n = n >> 1; for(i = 1; i <= n; ++i){ if(!vis[i]) ss.push(i); if(vis[i + n]) ss.push(i + n); } printf("%d\n",ss.size()); while(!ss.empty()){ temp = ss.top(); ss.pop(); if(temp <= n) printf("%d -\n",temp); else printf("%d +\n",temp - n); }}int main(){ while(EOF != scanf("%d%d",&n,&m)) solve(); return 0;}
使用SAP + GAP 优化：(79MS)
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <climits>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define mm(a) memset((a),0,sizeof((a)))#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 220;int n, m, map[MAXN][MAXN], dis[MAXN], gap[MAXN];int src, des;bool vis[MAXN];stack <int> ss;void init(){ mm(dis);mm(gap);mm(map);mm(vis);}int sap(int u,int flow){ if(u == des) return flow; int ans = 0, i, t; for(i = 0; i <= n + 1; ++i) if(map[u][i] && dis[u] == dis[i] + 1){ t = sap(i, min(flow - ans, map[u][i])); map[u][i] -= t, map[i][u] += t,ans += t; if(ans == flow) return ans; } if(dis[src] >= n + 2) return ans; if(!--gap[dis[u]]) dis[src] = n + 2; ++gap[++dis[u]]; return ans;}void dfs(int p){ if(vis[p]) return ; vis[p] = true; for(int i = 0; i < n + 1; ++i) if(!vis[i] && map[p][i]) dfs(i);}void solve(){ int i, x, y, ans = 0, temp; init(); for(i = 1; i <= n; ++i) scanf("%d",&map[n + i][n * 2 + 1]); for(i = 1; i <= n; ++i) scanf("%d",&map[0][i]); for(i = 1; i <= m; ++i){ scanf("%d%d",&x,&y); map[x][y + n] = INF; } n = n << 1; src = 0, des = n + 1; for(gap[0] = n + 2; dis[src] < n + 2; ) ans += sap(src,INF); dfs(0); printf("%d\n",ans); n = n >> 1; for(i = 1; i <= n; ++i){ if(!vis[i]) ss.push(i); if(vis[i + n]) ss.push(i + n); } printf("%d\n",ss.size()); while(!ss.empty()){ temp = ss.top(); ss.pop(); if(temp <= n) printf("%d -\n",temp); else printf("%d +\n",temp - n); }}int main(){ while(scanf("%d%d",&n,&m)!=EOF) solve(); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。