1 条题解
-
0
#include<bits/stdc++.h> #define INF INT_MAX using namespace std; const int N=5e4+10,M=2.5e5+10; int n,m,st,ed,S,T; struct edge{ int x,y,c,pre; }a[M*2]; int alen,last[N],cur[N]; void ins(int x,int y,int c) { a[++alen]={x,y,c,last[x]}; last[x]=alen; } int f[N],h[N]; bool bfs() { memset(h,0,sizeof(h));h[S]=1; deque<int> q;q.push_back(S); while(!q.empty()) { int x=q.front();q.pop_front(); for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(!h[y]&&a[k].c) { h[y]=h[x]+1; q.push_back(y); } } } return h[T]; } int Dinic(int x,int f) { if(x==T) return f; int sx=0; for(int k=cur[x];k;k=a[k].pre) { cur[x]=k; int y=a[k].y; if(h[y]==h[x]+1&&a[k].c&&sx<f) { int sy=Dinic(y,min(a[k].c,f-sx)); a[k].c-=sy,a[k^1].c+=sy; sx+=sy; if(sx==f) break; } } if(sx==0) h[x]=0; return sx; } int main() { scanf("%d%d%d%d",&n,&m,&st,&ed); S=n+1,T=n+2; alen=1;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int x,y,u,v; scanf("%d%d%d%d",&x,&y,&u,&v); ins(x,y,v-u),ins(y,x,0); f[x]-=u,f[y]+=u; } int sum1=0,sum2=0; for(int i=1;i<=n;i++) { if(f[i]>0) ins(S,i,f[i]),ins(i,S,0),sum1+=f[i]; if(f[i]<0) ins(i,T,-f[i]),ins(T,i,0); } ins(ed,st,INF),ins(st,ed,0); while(bfs()) { memcpy(cur,last,sizeof(last)); sum2+=Dinic(S,INF); } if(sum1^sum2) puts("please go home to sleep"); else { for(int k=last[S];k;k=a[k].pre) a[k].c=a[k^1].c=0; for(int k=last[T];k;k=a[k].pre) a[k].c=a[k^1].c=0; sum2=a[alen].c; a[alen].c=a[alen-1].c=0; S=ed,T=st;int sum3=0; while(bfs()) { memcpy(cur,last,sizeof(last)); sum3+=Dinic(S,INF); } printf("%d\n",sum2-sum3); } return 0; }
- 1
信息
- ID
- 385
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 26
- 已通过
- 11
- 上传者