【ZOJ 2676】Network Wars 網(wǎng)絡(luò)戰(zhàn)爭(zhēng) 網(wǎng)絡(luò)流 01分?jǐn)?shù)規(guī)劃

2019-11-08 01:42:25

字體：大中小

供稿：網(wǎng)友

題目描述

　　Byteland的網(wǎng)絡(luò)包含n個(gè)服務(wù)器，由m條光纖連接。每一條光纖連接兩個(gè)服務(wù)器，數(shù)據(jù)能夠在光纖上雙向傳輸。網(wǎng)絡(luò)中的兩臺(tái)服務(wù)器極其重要，他們分別連接了全球網(wǎng)絡(luò)和總統(tǒng)府網(wǎng)絡(luò)。　　連接總統(tǒng)府網(wǎng)絡(luò)的服務(wù)器編號(hào)1，連接全球網(wǎng)絡(luò)的服務(wù)器編號(hào)n。最近，Max Traffic公司決定接管一些光纖，以便于他們了解總統(tǒng)府的用戶傳輸?shù)臄?shù)據(jù)。當(dāng)然他們想控制一些光纖，使得若想要下載從全球網(wǎng)絡(luò)傳輸?shù)娇偨y(tǒng)府網(wǎng)絡(luò)的任意數(shù)據(jù)，都必須經(jīng)過(guò)這些光纖中的至少一條。　　為了實(shí)施計(jì)劃，公司需要從供貨商那里購(gòu)買相應(yīng)的光纖。每一條光纖需要一定的花費(fèi)。由于公司的主要業(yè)務(wù)不是間諜活動(dòng)，而是想家庭用戶提供網(wǎng)絡(luò)連接，公司的管理層想要讓這次行動(dòng)成為絕佳的投資行為。因此公司想要購(gòu)買滿足上述要求的光纖，并且使得花費(fèi)盡可能小。也就是說(shuō)，如果公司總共花費(fèi)c購(gòu)買了k條光纖，公司想要最小化c/k的值。

題目大意

　　給定一個(gè)無(wú)向圖，選取一邊集E（必須包含割），使得所選邊集的邊權(quán)平均值最小。（多組數(shù)據(jù)）

數(shù)據(jù)范圍

　　(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分?jǐn)?shù)規(guī)劃，二分c/k的值，如果邊權(quán)小于二分的值，則可以無(wú)腦選擇，然后將沒(méi)被選擇的邊加進(jìn)網(wǎng)絡(luò)流中（權(quán)值要減去c/k），來(lái)一次最小割。從源點(diǎn)DFS一下，輸出兩端點(diǎn)不在同一集合的邊。

代碼

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#define Maxn 23333//數(shù)組大小隨緣開(kāi)的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的值，精讀太低就會(huì)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;}

求各位神犇給蒟蒻一點(diǎn)評(píng)論啊QAQ

上一篇：Linux輸入子系統(tǒng)

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