1 条题解

  • 0
    @ 2026-2-7 19:54:17
    #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
    上传者