poj 2391 Ombrophobic Bovines 网络流
二分答案+网络流判定，一定得拆点。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=2e2+9,inf=1e9;long long d[maxn][maxn];int n,m,sum;int level[maxn<<1],que[maxn<<1];int head[maxn<<1],lon;int now[maxn],limit[maxn];struct{ int next,to,c;}e[maxn*maxn<<1];void edgeini(){ memset(head,-1,sizeof(head)); lon=-1;}void edgemake(int from,int to,int c){ e[++lon].c=c; e[lon].to=to; e[lon].next=head[from]; head[from]=lon;}struct EE{ int from,to; long long w; bool operator <(const EE & xx) const { return w<xx.w; }}ee[maxn*maxn];void floyed(){ for(int i=1;i<=n;i++) d[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}bool makelevel(int s,int t){ memset(level,0,sizeof(level)); int front=1,end=0; que[++end]=s; level[s]=1; while(front<=end) { int u=que[front++];// cout<<u<<endl; if(u==t) return true; for(int k=head[u];k!=-1;k=e[k].next) { int v=e[k].to; if(!level[v]&&e[k].c) { que[++end]=v; level[v]=level[u]+1; } } } return false;}int dfs(int now,int t,int maxf){ if(t==now) return maxf; int ret=0; for(int k=head[now];k!=-1;k=e[k].next) { int u=e[k].to; if(e[k].c&&level[u]==level[now]+1) { int f=dfs(u,t,min(maxf-ret,e[k].c)); e[k].c-=f; e[k^1].c+=f; ret+=f; if(ret==maxf) return ret; } } return ret;}int maxflow(int s,int t){ int ret=0; while(makelevel(s,t)) { ret+=dfs(s,t,inf); } return ret;}void init(){ memset(d,50,sizeof(d));}bool chk(long long mid){ edgeini(); for(int i=1;i<=n;i++) { edgemake(0,i,now[i]); edgemake(i,0,0); edgemake(i+n,n+n+1,limit[i]); edgemake(1+n+n,i+n,0); } for(int i=1;i<=n*n;i++) if(ee[i].w<=mid) { edgemake(ee[i].from,ee[i].to+n,inf); edgemake(ee[i].to+n,ee[i].from,0); } int ret=maxflow(0,n+n+1); return ret==sum;}int main(){// freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { init(); sum=0; for(int i=1;i<=n;i++) { scanf("%d%d",&now[i],&limit[i]); sum+=now[i]; } for(int i=1,from,to;i<=m;i++) { long long w; scanf("%d%d",&from,&to); scanf("%lld",&w); d[from][to]=min(w,d[from][to]); d[to][from]=d[from][to]; } floyed(); int tt=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { tt++; ee[tt].from=i; ee[tt].to=j; ee[tt].w=d[i][j]; }// cout<<n*n<<endl; sort(ee+1,ee+1+tt); long long l=0,r=0,mid; for(int i=1;i<=n*n;i++) if(ee[i].w<1e12) r=max(r,ee[i].w); while(l<r) {// printf("%I64d %I64d\n",l,r); mid=l+r>>1; if(chk(mid)) r=mid; else l=mid+1; } if(chk(l)) cout<<l<<endl; else printf("-1\n");// cout<<lon<<endl;// maxflow(0,n+1); } return 0;}