Code:
#include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 1000000 #define inf 10000000000000 #define ll long long using namespace std; namespace Dinic{ struct Edge{ int from,to,cap; Edge(int u=0,int v=0,int c=0):from(u),to(v),cap(c){} }; vector<int>G[500]; vector<Edge>edges; queue<int>Q; int vis[500],d[500],curr[500]; int s,t; void addedge(int u,int v,int c){ edges.push_back(Edge(u,v,c)),edges.push_back(Edge(v,u,0)); int m=edges.size(); G[u].push_back(m-2),G[v].push_back(m-1); } int BFS(){ memset(vis,0,sizeof(vis)); d[s]=0,vis[s]=1, Q.push(s); while(!Q.empty()){ int u=Q.front();Q.pop(); for(int sz=G[u].size(),i=0;i<sz;++i){ Edge r=edges[G[u][i]]; if(!vis[r.to]&&r.cap>0) { vis[r.to]=1,d[r.to]=d[u]+1; Q.push(r.to); } } } return vis[t]; } int dfs(int x,int cur){ if(x==t) return cur; int f,flow=0; for(int sz=G[x].size(),i=curr[x];i<sz;++i){ curr[x]=i; Edge r=edges[G[x][i]]; if(d[r.to]==d[x]+1&&r.cap>0){ f=dfs(r.to,min(cur,r.cap)); cur-=f,flow+=f,edges[G[x][i]].cap-=f,edges[G[x][i]^1].cap+=f; } if(cur<=0) break; } return flow; } int maxflow(){ int flow=0; while(BFS()) memset(curr,0,sizeof(curr)),flow+=dfs(s,10000000); return flow; } void re(){ for(int i=0;i<500;++i) G[i].clear(); edges.clear(); } }; #define row1(i) (i) #define row2(i) (i+n) int C[maxn],num[maxn],sums=0,n; long long d[500][500]; bool check(ll tmp) { Dinic::re(); int s=0,t=row2(n+1); Dinic::s=s,Dinic::t=t; for(int i=1;i<=n;++i) { if(num[i]) Dinic::addedge(s,row1(i),num[i]); if(C[i]) Dinic::addedge(row2(i),t,C[i]); } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(i!=j && d[i][j]<=tmp) Dinic::addedge(row1(i), row2(j), 10000000); } return Dinic::maxflow() >= sums; } int main() { // setIO("input"); int m; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d%d",&num[i],&C[i]),sums+=num[i]; for(int i=0;i<=230;++i) for(int j=0;j<=230;++j) d[i][j]=inf; for(int i=0;i<=230;++i) d[i][i]=0; for(int i=1;i<=m;++i) { int u,v; ll c; scanf("%d%d%lld",&u,&v,&c); if(u!=v) d[u][v]=d[v][u]=min(d[u][v],c); } 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]); ll l=0,r=100000000000000,ans=-1; while(l<=r) { ll mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%lld\n",ans); return 0; }
BZOJ 1738: [Usaco2005 mar]Ombrophobic Bovines 发抖的牛 网络流_二分_Floyd
原文:https://www.cnblogs.com/guangheli/p/10972336.html