【USACO4.4.2】追查壞牛奶網(wǎng)絡(luò)流

2019-11-08 02:01:19

字體：大中小

供稿：網(wǎng)友

題目大意

你第一天接手光明牛奶公司就發(fā)生了一件倒霉的事情：公司不小心發(fā)送了一批壞牛奶。很不幸，你發(fā)現(xiàn)這件事的時(shí)候，壞牛奶已經(jīng)進(jìn)入了送貨網(wǎng)。這個(gè)送貨網(wǎng)很大，而且關(guān)系復(fù)雜。你知道這批牛奶要發(fā)給哪個(gè)零售商，但是要把這批牛奶送到他手中有許多種途徑。送貨網(wǎng)由一些倉庫和運(yùn)輸卡車組成，每輛卡車都在各自固定的兩個(gè)倉庫之間單向運(yùn)輸牛奶。在追查這些壞牛奶的時(shí)候，有必要保證它不被送到零售商手里，所以必須使某些運(yùn)輸卡車停止運(yùn)輸，但是停止每輛卡車都會(huì)有一定的經(jīng)濟(jì)損失。你的任務(wù)是，再保證壞牛奶不送到零售商的前提下，制定出停止卡車運(yùn)輸?shù)姆桨福箵p失最小。求有向圖最小割集，在滿足代價(jià)最小的情況下，則滿足停止卡車數(shù)量最小的方案，如果卡車數(shù)量相同，則輸出字典序最小的方案。

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

(2<=N<=32)N為點(diǎn)數(shù)(0<=M<=1000)M為邊數(shù)

樣例輸入

4 51 3 1003 2 502 4 601 2 402 3 80

樣例輸出

60 13

代碼

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#define Maxn 55using 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,GAP[Maxn],dis[Maxn],h[Maxn];int Map[55][55],f[55][55],ans[6666],flag=0;struct NODE{int fr,to,v,pos;}w[1005];int SAP(int x,int Maxflow){ if(x==T)return Maxflow; int tmp=Maxflow; for(int i=1;i<=n;i++){ int y=i; int flow=min(tmp,f[x][y]); if(flow&&dis[x]==dis[y]+1){ int ret=SAP(y,flow); tmp-=ret; f[x][i]-=ret; f[i][x]+=ret; if(!tmp||dis[S]==N)return Maxflow-tmp; } } if(--GAP[dis[x]]==0)dis[S]=N; else GAP[++dis[x]]++; return Maxflow-tmp;}int SAP(){ memset(dis,0,sizeof(dis)); memset(GAP,0,sizeof(GAP)); GAP[0]=N; int Ans=0; while(dis[S]<N)Ans+=SAP(S,1<<30); return Ans;}bool cmp(NODE a,NODE b){return a.v>b.v;}int main(){ memset(Map,0,sizeof(Map)); memset(f,0,sizeof(f)); N=n=Getint(); m=Getint(); S=1;T=n; for(int i=1;i<=m;i++){ int x=Getint(),y=Getint(),v=Getint(); f[x][y]+=v; w[i]=(NODE){x,y,v,i}; } sort(w+1,w+m+1,cmp);//按邊權(quán)值由大到小排序，從而滿足停止線路最少的條件 memcpy(Map,f,sizeof(f));//map數(shù)組為備份 int Ans=SAP(); cout<<Ans<<" "; for(int i=1;i<=m;i++){//枚舉是否斷邊 if(f[w[i].fr][w[i].to])continue; memcpy(f,Map,sizeof(Map)); f[w[i].fr][w[i].to]-=w[i].v; int tmp=Ans; Ans=SAP(); if(Ans+w[i].v==tmp){ Map[w[i].fr][w[i].to]-=w[i].v;//如果滿足條件，則map數(shù)組也斷掉這條邊 ans[++flag]=w[i].pos; if(!Ans)break; } } cout<<flag<<"/n"; sort(ans+1,ans+flag+1);//排序輸出 for(int i=1;i<=flag;i++)cout<<ans[i]<<"/n"; return 0;}

上一篇：狀態(tài)機(jī)學(xué)習(xí) 解析四則運(yùn)算式語法分析

下一篇：登錄token值的demo