- 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;
- }
来源: http://www.bubuko.com/infodetail-3081929.html