2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct edge{int x,y,c,pre,other;}a[1110000];int alen,last[410],h[410],st,ed; void ins(int x,int y,int c) { ++alen;a[alen]=edge{x,y,c,last[x],alen+1};last[x]=alen; ++alen;a[alen]=edge{y,x,0,last[y],alen-1};last[y]=alen; } deque<int>Q; bool bh() { memset(h,0,sizeof(h));h[st]=1; Q.clear();Q.push_back(st); while(!Q.empty()) { int x=Q.front(); for(int k=last[x];k>0;k=a[k].pre) { int y=a[k].y; if(h[y]==0&&a[k].c>0) { h[y]=h[x]+1; Q.push_back(y); } } Q.pop_front(); } return h[ed]>0; } int findflow(int x,int f) { if(x==ed)return f; int sx=0; for(int k=last[x];k>0;k=a[k].pre) { int y=a[k].y; if(h[y]==(h[x]+1)&&f>sx&&a[k].c>0) { int sy=findflow(y,min(a[k].c,f-sx)); a[k].c-=sy;a[a[k].other].c+=sy; sx=sx+sy; } } if(sx==0)h[x]=0; return sx; } int n,m,SA,A[210],B[210]; LL Map[210][210]; bool check(LL Maxd) { st=n*2+1;ed=st+1; alen=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++)ins(st,i,A[i]); for(int i=1;i<=n;i++)ins(i,n+i,A[i]); for(int i=1;i<=n;i++)ins(n+i,ed,B[i]); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)if(j!=i) { if(Map[i][j]<=Maxd)ins(i,n+j,A[i]); } } int s=0;while(bh())s+=findflow(st,SA); return s==SA; } int main() { scanf("%d%d",&n,&m); SA=0;for(int i=1;i<=n;i++)scanf("%d%d",&A[i],&B[i]),SA+=A[i]; memset(Map,63,sizeof(Map)); for(int i=1;i<=m;i++) { int x,y,d;scanf("%d%d%d",&x,&y,&d); if(Map[x][y]>d)Map[x][y]=Map[y][x]=d; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++)if(i!=k) for(int j=1;j<=n;j++)if((j!=i)&&(j!=k)) if(Map[i][k]+Map[k][j]<Map[i][j])Map[i][j]=Map[i][k]+Map[k][j]; LL L=0,R=(LL)1000000000*1500,ans=-1; while(L<=R) { LL mid=(L+R)/2; if(check(mid)==1)ans=mid,R=mid-1; else L=mid+1; } printf("%lld",ans); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:49:12
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct edge{int x,y,c,pre,other;}a[1110000];int alen,last[410],h[410],st,ed; void ins(int x,int y,int c) { ++alen;a[alen]=edge{x,y,c,last[x],alen+1};last[x]=alen; ++alen;a[alen]=edge{y,x,0,last[y],alen-1};last[y]=alen; } deque<int>Q; bool bh() { memset(h,0,sizeof(h));h[st]=1; Q.clear();Q.push_back(st); while(!Q.empty()) { int x=Q.front(); for(int k=last[x];k>0;k=a[k].pre) { int y=a[k].y; if(h[y]==0&&a[k].c>0) { h[y]=h[x]+1; Q.push_back(y); } } Q.pop_front(); } return h[ed]>0; } int findflow(int x,int f) { if(x==ed)return f; int sx=0; for(int k=last[x];k>0;k=a[k].pre) { int y=a[k].y; if(h[y]==(h[x]+1)&&f>sx&&a[k].c>0) { int sy=findflow(y,min(a[k].c,f-sx)); a[k].c-=sy;a[a[k].other].c+=sy; sx=sx+sy; } } if(sx==0)h[x]=0; return sx; } int n,m,SA,A[210],B[210]; LL Map[210][210]; bool check(LL Maxd) { st=n*2+1;ed=st+1; alen=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++)ins(st,i,A[i]); for(int i=1;i<=n;i++)ins(i,n+i,A[i]); for(int i=1;i<=n;i++)ins(n+i,ed,B[i]); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)if(j!=i) { if(Map[i][j]<=Maxd)ins(i,n+j,A[i]); } } int s=0;while(bh())s+=findflow(st,SA); return s==SA; } int main() { scanf("%d%d",&n,&m); SA=0;for(int i=1;i<=n;i++)scanf("%d%d",&A[i],&B[i]),SA+=A[i]; memset(Map,63,sizeof(Map)); for(int i=1;i<=m;i++) { int x,y,d;scanf("%d%d%d",&x,&y,&d); if(Map[x][y]>d)Map[x][y]=Map[y][x]=d; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++)if(i!=k) for(int j=1;j<=n;j++)if((j!=i)&&(j!=k)) if(Map[i][k]+Map[k][j]<Map[i][j])Map[i][j]=Map[i][k]+Map[k][j]; LL L=0,R=(LL)1000000000*1500,ans=-1; while(L<=R) { LL mid=(L+R)/2; if(check(mid)==1)ans=mid,R=mid-1; else L=mid+1; } printf("%lld",ans); return 0; }
- 1