【USACO4.4.2】追查坏牛奶网络流

2019-11-08 02:01:19

字体：大中小

来源：转载

供稿：网友

题目大意

你第一天接手光明牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批坏牛奶。很不幸，你发现这件事的时候，坏牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些坏牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，再保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。求有向图最小割集，在满足代价最小的情况下，则满足停止卡车数量最小的方案，如果卡车数量相同，则输出字典序最小的方案。

数据范围

(2<=N<=32)N为点数(0<=M<=1000)M为边数

样例输入

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);//按边权值由大到小排序，从而满足停止线路最少的条件 memcpy(Map,f,sizeof(f));//map数组为备份 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数组也断掉这条边 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;}

上一篇：状态机学习解析四则运算式语法分析

下一篇：登录token值的demo