题意:有n个牛棚,现在每个牛棚都有ai牛,下雨的时候每一个牛棚可以放bi只牛才不会淋湿。把牛放入另一个牛棚需要一些时间。。问最短要多少时间。能把牛放到其他的牛盆里,牛才不会被淋湿。。
思路:网络流,开始的时候建了一个图,后来发现错了 ,无语。。。又是看别人的报告才过的,,还有自己到自己的路程应该是0,wa了一次,更纠结了。。
数据:http://ace.delos.com/MAR05_4.htm
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> using namespace std; #define LL long long const int N = 409; const int INF = 0x3f3f3f3f; int cur[N],gap[N],g[N][N],dist[N],pre[N]; LL dis[N][N]; int n,m,s1,t1; int sap() { int ret = 0,aug = INF,u,v; memset(gap,0,sizeof(gap)); memset(dist,0,sizeof(dist)); for(int i=0;i<=n;i++) cur[i] = i; u = pre[s1] = s1; gap[0] = n; while(dist[s1]<=n) { loop: for(v=cur[u];v<=n;v++) if(g[u][v]>0&&dist[u]==dist[v]+1) { cur[u] = v;aug = min(aug,g[u][v]); pre[v] = u; u = v; if(v==t1){ ret+=aug; for(u=pre[u];v!=s1;v=u,u=pre[u]) g[u][v]-=aug,g[v][u]+=aug; aug=INF; } goto loop; } int mind = n; for(v=1;v<=n;v++) if(g[u][v]>0&&mind>dist[v]) mind = dist[v],cur[u] =v; if(--gap[dist[u]]<=0) break; gap[dist[u] = mind+1]++; u = pre[u]; }return ret; } int tmp[N][N]; void floyd() { for(int i=1;i<s1;i++) for(int j=1;j<s1;j++) for(int k=1;k<s1;k++) if(dis[j][k]>dis[j][i]+dis[i][k]) dis[j][k] = dis[j][i]+dis[i][k]; } int main() { freopen("in.txt","r",stdin); int a,b,f,t,sum=0; scanf("%d%d",&a,&b); s1 = a*2+1,t1 = a*2+2;n=a*2+2; for(int i=1;i<=a;i++) { scanf("%d%d",&f,&t); g[s1][i] = f;sum+=f; g[i+a][t1] = t; } memset(dis,INF,sizeof(dis)); for(int i=1;i<=b;i++) { LL cc; scanf("%d%d%lld",&f,&t,&cc); if(dis[f][t]>cc) dis[f][t]=dis[t][f] = cc; } memcpy(tmp,g,sizeof(g)); for(int i=0;i<=a*2;i++) dis[i][i] = 0; ///没有这个过不了第三组数据,^_^ floyd(); LL l = 0,r = 1LL*INF*INF,mid; LL ans =-1; while(l<=r){ memcpy(g,tmp,sizeof(tmp)); mid = (l+r)>>1ll; for(int i=1;i<=a;i++) for(int j=1;j<=a;j++) if(dis[i][j]<=mid) { g[i][j+a] = INF; } int k = sap(); if(sum==k) ans = mid,r = mid - 1; else l = mid+1; } cout<<ans<<endl; return 0; }