【ZOJ 2676】Network Wars 网络战争网络流 01分数规划

2019-11-08 01:42:25

字体：大中小

来源：转载

供稿：网友

题目描述

　　Byteland的网络包含n个服务器，由m条光纤连接。每一条光纤连接两个服务器，数据能够在光纤上双向传输。网络中的两台服务器极其重要，他们分别连接了全球网络和总统府网络。　　连接总统府网络的服务器编号1，连接全球网络的服务器编号n。最近，Max Traffic公司决定接管一些光纤，以便于他们了解总统府的用户传输的数据。当然他们想控制一些光纤，使得若想要下载从全球网络传输到总统府网络的任意数据，都必须经过这些光纤中的至少一条。　　为了实施计划，公司需要从供货商那里购买相应的光纤。每一条光纤需要一定的花费。由于公司的主要业务不是间谍活动，而是想家庭用户提供网络连接，公司的管理层想要让这次行动成为绝佳的投资行为。因此公司想要购买满足上述要求的光纤，并且使得花费尽可能小。也就是说，如果公司总共花费c购买了k条光纤，公司想要最小化c/k的值。

题目大意

　　给定一个无向图，选取一边集E（必须包含割），使得所选边集的边权平均值最小。（多组数据）

数据范围

　　(2 <= n <= 100 , 1 <= m <= 400 )

样例输入

6 8 1 2 3 1 3 3 2 4 2 2 5 2 3 4 2 3 5 2 5 6 3 4 6 3

样例输出

4 3 4 5 6

解题思路

01分数规划，二分c/k的值，如果边权小于二分的值，则可以无脑选择，然后将没被选择的边加进网络流中（权值要减去c/k），来一次最小割。从源点DFS一下，输出两端点不在同一集合的边。

代码

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#define Maxn 23333//数组大小随缘开的233#define Maxe 23333using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int n,m,S,T,N,cnt=0,x[Maxn],y[Maxn],v[Maxn],h[Maxn],GAP[Maxn],dis[Maxn];bool vis[Maxn],used[Maxn];struct node{int to,next,v,pair;}e[Maxe];void AddEdge(int X,int Y,int v,int pa){e[cnt]=(node){Y,h[X],v,pa};h[X]=cnt;}void AddEdge(int X,int Y,int v){AddEdge(X,Y,v,++cnt+1);AddEdge(Y,X,0,++cnt-1);}int SAP(int X,int Maxflow){ if(X==T)return Maxflow; int tmp=Maxflow; for(int p=h[X];p;p=e[p].next){ int y=e[p].to; int flow=min(tmp,e[p].v); if(flow&&dis[X]==dis[y]+1){ int ret=SAP(y,flow); tmp-=ret; e[p].v-=ret; e[e[p].pair].v+=ret; if(!tmp||dis[S]==n)return Maxflow-tmp; } } if(--GAP[dis[X]]==0)dis[S]=n; else GAP[++dis[X]]++; return Maxflow-tmp;}double SAP(){ memset(GAP,0,sizeof(GAP)); memset(dis,0,sizeof(dis)); GAP[0]=n; S=1,T=n; int Ans=0; while(dis[S]<n)Ans+=SAP(S,1<<30); return Ans;}bool Check(double k){ memset(e,0,sizeof(e)); memset(h,0,sizeof(h)); memset(used,0,sizeof(vis)); cnt=0; double ret=0.0; for(int i=1;i<=m;i++){ if(v[i]<=k){used[i]=1;ret+=v[i]-k;} else{AddEdge(x[i],y[i],v[i]-k);AddEdge(y[i],x[i],v[i]-k);}//这里的v[i]要减去K } return SAP()+ret>0;}void Init(){ for(int i=1;i<=m;i++)x[i]=Getint(),y[i]=Getint(),v[i]=Getint();}void Dfs(int x){ vis[x]=true; for(int p=h[x];p;p=e[p].next){ int y=e[p].to; if(!vis[y]&&e[p].v)Dfs(y); }}void Solve(){ double L=0,r=1e9; while(L+1e-8<r){//二分C/K的值，精读太低就会WA。。。 double mid=(L+r)/2; if(Check(mid))L=mid; else r=mid; } memset(vis,0,sizeof(vis)); Dfs(S); for(int i=1;i<=m;i++)if(vis[x[i]]!=vis[y[i]])used[i]=true; int Ans=0; for(int i=1;i<=m;i++)Ans+=used[i]; cout<<Ans<<"/n"; for(int i=1;i<=m;i++)if(used[i])cout<<i<<" "; cout<<"/n";}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ Init(); Solve(); } return 0;}

求各位神犇给蒟蒻一点评论啊QAQ

上一篇：Linux输入子系统

下一篇：小雷的冰茶几——并查集