首页 > 代码库 > zoj 2676 Network Wars(最小割,01分数规划)
zoj 2676 Network Wars(最小割,01分数规划)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2676
大致题意:给出一个带权无向图,每条边有一个边权wi,求将S和T分开的一个割边集C,使得该割边集的平均边权最小,即最小化∑wi / |C| 。
详见amber关于最小割模型的论文
思路:amber论文中详细讲解了如何转化成函数及建图,值得注意的是当边被重新赋权后,对于wi < 0 的边权,该边必然在最小割中,不必再建边,直接加入最大流中即可,因为求最小割时边权都为正值。
最后输出的是所选割边的序号。求割边无非是从源点dfs,每次走残量网络中流量大于0的边并标记端点,最后判断边的两个端点一个标记一个未标记,那么该边便是割边。
这题我TLE了13次,最后是因为Dinic的原因,可能之前的那个模板耗时太长了。改成了学长的Dinic,瞬间就A了。
#include <stdio.h> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #define LL long long #define _LL __int64 #define eps 1e-7 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 210; const int maxm = 6000; int s,t; struct node { int u,v; double w; int next; int re; }p[maxm],edge[maxm]; int n,m; int cnt,head[maxn]; int dist[maxn],vis[maxn]; void init() { cnt = 0; memset(head,-1,sizeof(head)); } void add(int u, int v, double w) { edge[cnt] = (struct node){u,v,w,head[u],cnt+1}; head[u] = cnt++; edge[cnt] = (struct node){v,u,0,head[v],cnt-1}; head[v] = cnt++; } bool bfs() { queue <int> que; memset(dist, 0, sizeof(dist)); memset(vis, 0, sizeof(vis)); while(!que.empty()) que.pop(); vis[s] = 1; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].w && !vis[v]) { que.push(v); vis[v] = 1; dist[v] = dist[u]+1; } } } if(dist[t] == 0) return false; return true; } double dfs(int u, double delta) { if(u == t) return delta; double ret = 0,tmp; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].w && dist[edge[i].v] == dist[u]+1 && (tmp = dfs(v,min(delta,edge[i].w)))) { edge[i].w -= tmp; edge[edge[i].re].w += tmp; return tmp; } } if(!ret) dist[u] = -1; return ret; } double Dinic() { double ret = 0,res; while(bfs()) { while(res = dfs(s,INF)) ret += res; } return ret; } bool ok(double mid) { init(); double flow = 0; for(int i = 1; i <= m; i++) { if(p[i].w > mid) { add(p[i].u,p[i].v,p[i].w-mid); add(p[i].v,p[i].u,p[i].w-mid); } else flow += p[i].w - mid; } flow += Dinic(); if(flow > eps) return true; else return false; } void dfs_cut(int u) { vis[u] = 1; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(!vis[v] && edge[i].w > 0) { dfs_cut(v); } } } int main() { int item = 0; while(~scanf("%d %d",&n,&m)) { s = 1; t = n; item += 1; if(item >= 2) printf("\n"); double low = INF,high = 0,mid; for(int i = 1; i <= m; i++) { scanf("%d %d %lf",&p[i].u, &p[i].v, &p[i].w); low = min(low,p[i].w); high = max(high,p[i].w); } while( fabs(high - low) > eps) { mid = (high + low)/2.0; if( ok(mid) ) low = mid; else high = mid; } memset(vis,0,sizeof(vis)); dfs_cut(1); int count = 0; int ans[maxm]; for(int i = 1; i <= m; i++) { if(vis[p[i].u] + vis[p[i].v] == 1 || p[i].w <= mid) ans[++count] = i; } printf("%d\n",count); for(int i = 1; i <= count-1; i++) printf("%d ",ans[i]); printf("%d\n",ans[count]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。