题目链接：https://vjudge.net/problem/Gym-101908G 转自：https://blog.csdn.net/liexss/article/details/83623213 题意：给你一些接受点和提供点，然后给你一些接受点到提供点的边和所需时间，求最短时间（同时运输）将所有接受点装满，输出所需时间。 思路：**二分时间，然后把满足时间的点加入边，跑网络流即可。**一开始以为是最小费用最大流，可能是double的问题，样例都过不了，并且可能超时。
#include <bits/stdc++.h> using namespace std; const int maxn=2500; const int inf1=1e9+5; int ax[1100],bn[1100]; struct NODE { int x,y,w; } node[21000]; int n1,m1,k,sum1,sum2; struct edge { int from,to,cap,flow; }; struct dinic { int n, m,s,t; vector <edge> gg; vector <int> ggg[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int l) { gg.clear(); for(int i=0; i<=l; i++) { ggg[i].clear(); } } void add(int from,int to,int cap) { gg.push_back((edge) { from,to,cap,0 }); gg.push_back((edge) { to,from,0,0 }); m=gg.size(); ggg[from].push_back(m-2); ggg[to].push_back(m-1); } bool bfs() { memset(vis,0,sizeof(vis)); queue<int> q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0; i<ggg[x].size(); i++) { edge &e=gg[ggg[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0) { return a; } int flow=0,f; for(int &i=cur[x]; i<ggg[x].size(); i++) { edge &e=gg[ggg[x][i]]; if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; gg[ggg[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow; } int maxflow(int s,int t) { this->s=s; this->t=t; int flow=0; while(bfs()) { memset(cur,0,sizeof(cur)); flow+=dfs(s,inf1); } return flow; } } din; bool check(int mid) { din.init(2100); int s=0,t=n1+m1+1; for(int i=1; i<=m1; i++) { din.add(s,i,bn[i]); } for(int i=1; i<=n1; i++) { din.add(m1+i,t,ax[i]); } for(int i=0; i<k; i++) { if(node[i].w<=mid) { din.add(node[i].y,m1+node[i].x,ax[node[i].x]); } } if(din.maxflow(s,t)>=sum1) return true; return false; } int main() { scanf("%d%d%d",&n1,&m1,&k); sum1=0,sum2=0; for(int i=1; i<=n1; i++) { scanf("%d",&ax[i]); sum1+=ax[i]; } for(int i=1; i<=m1; i++) { scanf("%d",&bn[i]); sum2+=bn[i]; } if(sum1>sum2) { printf("-1\n"); return 0; } for(int i=0; i<k; i++) { scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w); } int l=0,r=1e6; int ans=-1; while(l<=r) { int mid=l+(r-l)/2; if(check(mid)) { ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); return 0; }