1 条题解
-
0
#include<cstdio> #include<cstring> using namespace std; struct node { int y,c,next,other,f; }a[210000];int last[1000],len,n,m,st,ed,stt,edd,d[1000]; int stl[1000],edl[1000]; void ins(int x,int y,int c,int flog) { len++; a[len].y=y;a[len].c=c;a[len].f=flog; a[len].next=last[x];last[x]=len; len++; a[len].y=x;a[len].c=0;a[len].f=0; a[len].next=last[y];last[y]=len; a[len-1].other=len; a[len].other=len-1; } int list[1100],head,tail,h[2000]; bool bt(int l,int r) { memset(h,0,sizeof(h));h[l]=1; head=1;tail=2;list[head]=l; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(a[k].c>0 && h[y]==0) { h[y]=h[x]+1; list[tail++]=y; } } head++; } return h[r]!=0; } inline int mymin(int x,int y){return x<y?x:y;} int find(int x,int f,int lr) { if(x==lr)return f; int ans=0,t=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(a[k].c>0 && h[y]==h[x]+1 && ans<f) { ans+=t=find(y,mymin(a[k].c,f-ans),lr); a[k].c-=t;a[a[k].other].c+=t; } } if(ans==0)h[x]=0; return ans; } int main() { scanf("%d%d%d%d",&n,&m,&st,&ed); for(int i=1;i<=m;i++) { int x,y,l,r;scanf("%d%d%d%d",&x,&y,&l,&r); ins(x,y,r-l,i);d[x]-=l;d[y]+=l; } stt=0;edd=n+1; for(int i=1;i<=n;i++) { if(d[i]<0) { ins(i,edd,-d[i],0); stl[++stl[0]]=len-1; } else { ins(stt,i,d[i],0); edl[++edl[0]]=len-1; } } ins(ed,st,999999999,0); int ans=0; while(bt(stt,edd)==true)ans+=find(stt,999999999,edd); bool bk=true; for(int i=1;i<=stl[0];i++) { if(a[stl[i]].c!=0) { bk=false;break; } } for(int i=1;i<=edl[0];i++) { if(a[edl[i]].c!=0) { bk=false;break; } } if(bk==false)printf("please go home to sleep\n"); else { ans=a[a[last[ed]].other].c; for(int i=1;i<=len;i++) { if(a[i].f==0)a[i].c=0; } while(bt(st,ed)==true)ans+=find(st,999999999,ed); printf("%d\n",ans); } return 0; }
- 1
信息
- ID
- 384
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 18
- 已通过
- 11
- 上传者