设为首页 加入收藏

TOP

zoj 2676 Network Wars(最小割，01分数规划)
2015-07-24 07:08:26 来源: 作者: 【大 中 小】 浏览:78次
Tags：zoj 2676 Network Wars 最小 01分数 规划

?

大致题意：给出一个带权无向图，每条边有一个边权wi,求将S和T分开的一个割边集C，使得该割边集的平均边权最小，即最小化∑wi / |C| 。

?

详见amber关于最小割模型的论文

?

思路：amber论文中详细讲解了如何转化成函数及建图，值得注意的是当边被重新赋权后,对于wi < 0 的边权，该边必然在最小割中，不必再建边，直接加入最大流中即可，因为求最小割时边权都为正值。

最后输出的是所选割边的序号。求割边无非是从源点dfs,每次走残量网络中流量大于0的边并标记端点，最后判断边的两个端点一个标记一个未标记，那么该边便是割边。

这题我TLE了13次，最后是因为Dinic的原因，可能之前的那个模板耗时太长了。改成了学长的Dinic,瞬间就A了。

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #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 
            
              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( ); 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 ,count); for(int i = 1; i <= count-1; i++) printf(%d ,ans[i]); printf(%d ,ans[count]); } return 0; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：ZOJ 3765 Lights Splay Tree的几.. 下一篇：hdu3853 loops cf148D

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: