poj 2125 最小割解决 "最小点权覆盖问题" +输出解(割边集)

发布时间:2017-3-28 10:21:38 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 2125 最小割解决 "最小点权覆盖问题" +输出解(割边集)",主要涉及到poj 2125 最小割解决 "最小点权覆盖问题" +输出解(割边集)方面的内容,对于poj 2125 最小割解决 "最小点权覆盖问题" +输出解(割边集)感兴趣的同学可以参考一下。

题意:给你一幅有向图, 对于点i删除所有进入该点的边就要支付费用W[i]+(情况1), 删除所有从该点出发的边就要支付费用W[i]-,问删除图中的所有边至少需要多少费用(情况2)。 分析:首先我们根据题意,选点就能删除一些边, 那么这可以看成是“用点去覆盖边”, 这里无非是把边分成了2类, 我们可以把原来的点进行拆点,那么就完完全全等价于“用点去覆盖边",如果支付费用都为1,那么这就是”最小点覆盖集“问题,但这题费用不确定,那么这就是“最小点权覆盖集”问题, 借助二分匹配的思想,我们可以引入“最小割”来解决“最小点权覆盖”问题。 建图:拆点,左点阵为情况2的点, 右点阵为情况1的点,右点阵跟汇点T连流量为W+,左点阵跟源点S连费用为W-, 对于输入的边<u, v> 连边 (u, v+n)费用为无穷大inf。跑一边最大流,求出最小费用。 输出解:最要我们找到一个满足条件的割边集(注意不是所有割边, 因为有一条流已经经过了一条割边,那么下面一条割边就不用选了,这样费用才是最小的),那么就能输出解了。怎么找出割边呢?我们可以在残余网络里走流,如果有一条边是割边,那么之后就流不过去了,不是割边还能继续流,具体实现我们可以从源点S用dfs搜出能走到的点标记vis[] =1, 那么对于边<u,v> 只要 vis[u] = 1 && vis[v] = 0 那就是割边了。 总结:二分匹配的题都可以用最大流来解,在二分图中 有 “最小点覆盖集”和“最打独立集”,如果有了点权,那么就要用最大流(最小割)来解决 “最小点权覆盖集”(最小割)和“最大点权独立集”(最大流)问题。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 206; const int maxm = 10404; const int inf = 1e9; int n, m, N, S, T; struct Edge { int v, c, next; Edge(int v, int c, int next) : v(v), c(c), next(next) { } Edge() { } } edge[maxm]; int head[maxn], E; void add(int s, int t, int c) { edge[E] = Edge(t, c, head[s]); head[s] = E++; edge[E] = Edge(s, 0, head[t]); head[t] = E++; } void init() { memset(head, -1, sizeof(head)); E = 0; } int gap[maxn], dis[maxn], pre[maxn], cur[maxn]; int sap(int s, int t, int n) // s 源点,t汇点,n顶点总数 { int i; for(i = 0; i <= n; i++) { dis[i] = gap[i] = 0; cur[i] = head[i]; } gap[0] = n; int u = pre[s] = s, maxf = 0, aug = inf, v; while(dis[s] < n) { loop: for(i = cur[u]; ~i; i = edge[i].next) { v = edge[i].v; if(edge[i].c && dis[u] == dis[v] + 1) { aug = min(aug, edge[i].c); pre[v] = u; cur[u] = i; u = v; if(u == t) { while(u != s) { u = pre[u]; edge[cur[u]].c -= aug; edge[cur[u] ^ 1].c += aug; } maxf += aug; aug = inf; } goto loop; } } int d = n; for(i = head[u]; ~i; i = edge[i].next) { v = edge[i].v; if(edge[i].c && dis[v] < d) { d = dis[v]; cur[u] = i; } } if(!(--gap[dis[u]])) break; ++gap[dis[u] = d + 1]; u = pre[u]; } return maxf; } bool vis[maxn]; void dfs(int u) { vis[u] = 1; for(int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; if(!vis[v] && edge[i].c) dfs(v); } } int cnt, res[maxn]; void debug() { int i; for(i = head[7]; ~i; i = edge[i].next) printf("v = %d\n", edge[i].v); } int main() { int i; while(~scanf("%d%d", &n, &m)) { N = n << 1; init(); S = 0; T = N+1; int x, y; for(i = 1; i <= n; i++) { scanf("%d", &x); add(i+n, T, x); } for(i = 1; i <= n; i++) { scanf("%d", &x); add(S, i, x); } while(m--) { scanf("%d%d", &x, &y); add(x, y + n, inf); } printf("%d\n", sap(S, T, T+1)); //dfs memset(vis, 0, sizeof(vis)); dfs(S); //枚举所有可能是割边的边 (与S或与T连的边) cnt = 0; for(i = head[S]; ~i; i = edge[i].next) { int v = edge[i].v; if(vis[S] && !vis[v]) res[cnt++] = v; } for(i = head[T]; ~i; i = edge[i].next) { int v = edge[i].v; if(vis[v] && !vis[T]) res[cnt++] = v; } printf("%d\n", cnt); for(i = 0; i < cnt; i++) if(res[i] <= n) printf("%d -\n", res[i]); else printf("%d +\n", res[i]-n); } return 0; }

上一篇:常用log4j配置
下一篇:windows下的环境搭建配置redis

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款