1 条题解
-
0
#include<cstdio> #include<cstring> using namespace std; struct node { int y,c,next,other; }a[30000];int last[410],len,n,m; struct bian { int x,y,l,r,id; }b[30000]; struct node1 { int a[410],len; }stl,edl;int stt,edd,rd[410],cd[410]; void ins(int x,int y,int c) { len++; a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len; len++; a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len; a[len].other=len-1; a[len-1].other=len; } int list[410],head,tail,h[410]; bool bt() { memset(h,0,sizeof(h));h[stt]=1; head=1;tail=2;list[head]=stt; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==0 && a[k].c>0) { h[y]=h[x]+1; list[tail++]=y; } } head++; } return h[edd]!=0; } inline int mymin(int x,int y){return x<y?x:y;} int find(int x,int f) { if(x==edd)return f; int t=0,ans=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(f-ans,a[k].c)); a[k].c-=t;a[a[k].other].c+=t; } } return ans; } int main() { scanf("%d%d",&n,&m); stt=0;edd=n+1; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&b[i].x,&b[i].y,&b[i].l,&b[i].r); ins(b[i].x,b[i].y,b[i].r-b[i].l);rd[b[i].y]+=b[i].l;cd[b[i].x]+=b[i].l;b[i].id=len; } for(int i=1;i<=n;i++) { int p=rd[i]-cd[i]; if(p>=0) { ins(stt,i,p); stl.a[++stl.len]=len-1; } else { ins(i,edd,-p); edl.a[++edl.len]=len-1; } } int ans=0; while(bt()==true) { ans+=find(stt,999999999); } bool bk=true; for(int i=1;i<=stl.len;i++) { if(a[stl.a[i]].c!=0) { bk=false; break; } } for(int i=1;i<=edl.len;i++) { if(a[edl.a[i]].c!=0) { bk=false; break; } } if(bk==false)printf("NO\n"); else { printf("YES\n"); for(int i=1;i<=m;i++)printf("%d\n",b[i].l+a[b[i].id].c); } return 0; }
- 1
信息
- ID
- 383
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 19
- 已通过
- 11
- 上传者