1 条题解
-
0
#include <bits/stdc++.h>//优化了当前弧) using namespace std; typedef long long LL; const int N=510,M=250000; struct node{int x,y;LL f; int pre;}a[M];int alen,last[N],cur[N]; void ins(int x,int y,LL f) { alen++;a[alen]=node{x,y,f,last[x]};last[x]=alen; alen++;a[alen]=node{y,x,0,last[y]};last[y]=alen; } int h[N],st,ed,n,m; bool bfs() { deque<int>q;q.clear(); memset(h,0,sizeof(h));h[st]=1; q.push_back(st); while(!q.empty()) { int x=q.front();q.pop_front(); for(int k=last[x];k>0;k=a[k].pre)if(a[k].f) { int y=a[k].y; if(h[y]==0) { h[y]=h[x]+1; q.push_back(y); } } } return h[ed]>0; } LL dinic(int x,LL f) { if(x==ed)return f; LL sx=0; for(int k=cur[x];k;k=a[k].pre)if(a[k].f) { int y=a[k].y; cur[x]=k;//k之前的边对于x已经没有意义 if(h[y]==h[x]+1) { LL sy=dinic(y,min(a[k].f,f-sx)); a[k].f-=sy;a[k^1].f+=sy; sx+=sy;if(sx==f)return f; } } if(sx==0)h[x]=0; return sx; } int main() { scanf("%d%d%d%d",&n,&m,&st,&ed);ed+=n; alen=1;memset(last,0,sizeof(last)); for(int i=1,x;i<=n;i++) { scanf("%d",&x); ins(i,n+i,x); } for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); ins(n+x,y,1LL<<60); ins(n+y,x,1LL<<60); } LL s=0; while( bfs() ) { memcpy(cur,last,sizeof(int)*(2*n+2)); s+=dinic(st,(LL)1<<62); } printf("%lld",s); return 0; }
- 1
信息
- ID
- 2816
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- 9
- 标签
- 递交数
- 13
- 已通过
- 5
- 上传者