zoj 2314 Reactor Cooling--无源汇有上下界最大流--递归sap

/*
	我也没有读题  刚学就直接搜的这类题    找了个简单的练习
	大致上好像是这么个意思   给你一个图   边有上下界
	求无源汇最大流   没有输出NO  有则输出 YES 并输出  各边的流量
*/
#include<iostream>
#include<string.h>
using namespace std;
const int N=205;
struct node
{
	int u,v;
}e[N*N];
int l[N][N],u[N][N],g[N][N],d[N],num[N],n,m,sink,src;
int min(int a,int b){return a<b?a:b;}
int sap(int u,int f)
{
	if(u==sink)  
        return f;  
    int v,mind=n+1,last=f,cost;
    for(v=0;v<=n+1;++v)  
    {  
        if(g[u][v]>0)//有流量  
        {  
            if(d[u]==d[v]+1)//有允许边  
            {  
                cost=sap(v,min(last,g[u][v]));  
                g[u][v]-=cost;//修改图  
                g[v][u]+=cost;  
                last-=cost;//修改剩余流量  
  
                if(d[src]>=n+2)//结束标志  
                    return f-last;  
  
                if(last==0)//使用完就退出  
                    break;  
            }  
            if(d[v]<mind)//下面更新距离的时候用  求其能连接到的最小距离   这个判断和上边的那个判断并列  因为他们是互斥的，只有当找不到允许边的时候才用得着mind  
                mind=d[v];  
        }  
    }  
  
    if(last==f)//流量没有使用  即  没有允许边  
    {  
        --num[d[u]];  
        if(num[d[u]]==0)//若出现断层  
        {  
            d[src]=n+2;  
        }  
        d[u]=mind+1;  
        ++num[d[u]];  
    }  
    return f-last;  
}
int main()
{
	int t,i,j,a,b,c,h;
	cin>>t;
	while(t--)
	{
		memset(g,sizeof(g));
		memset(l,sizeof(l));//曾经忘了初始化这俩   老是错 
		memset(u,sizeof(u));//
		cin>>n>>m;
		sink=n+1;
		src=0;
		for(i=1;i<=m;++i)
		{
			cin>>a>>b>>c>>h;
			e[i].u=a;//记录边   以便   存在答案是输出用
			e[i].v=b;
			l[a][b]=c;
			u[a][b]=h;
		}
		b=0;
		for(i=1;i<=n;++i)
		{
			a=0;
			for(j=1;j<=n;++j)
			{
				a+=l[j][i]-l[i][j];//统计  输入流比输出流多多少   
				g[i][j]=u[i][j]-l[i][j];
			}
			if(a>0)
				b+=g[0][i]=a;
			else g[i][n+1]=-a;
		}
		c=0;
		memset(d,sizeof(d));
		memset(num,sizeof(num));
		for(num[0]=n+2;d[0]<n+2;)
			c+=sap(0,0x7fffffff);
		if(c<b)
			cout<<"NO"<<endl;
		else
		{
			cout<<"YES"<<endl;
			for(i=1;i<=m;++i)
				cout<<(u[e[i].u][e[i].v]-g[e[i].u][e[i].v])<<endl;
		}
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!