题解 P4938 【War1】

小菜鸟 · 2019-06-26 21:18:01 · 题解

上一篇题解还是讲得过于简单了吧...

稍微详细一点。

每个点可以向其他点传输能量，显然是网络流。

同时，不能间接传输能量，

那么考虑拆点，将一个点拆成入点和出点，点与点之间只有入点能向出点传输能量。

这样就避免了已经被传输到出点的能量再被传到别处去。

然后就是套路，源点向第i个入点连A_i的边，第i个出点向汇点连B_i的边，每个入点向对应的出点连\inf的边。

输出方案的话，只要看看每条边上的剩余容量与原来差了多少，就知道起点向终点传输了多少能量了。

代码可以参考

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using std::queue;

const int N=1005,M=500005;

const int S=1003,T=1004;

int n,m;

int head[N],cur[N],level[N];

struct Edge
{
    int next,to,w,w0;
};
Edge E[M];

void __add(int u,int v,int w)
{
    static int tot=-1;
    E[++tot].next=head[u];
    E[tot].to=v;
    E[tot].w=E[tot].w0=w;
    head[u]=tot;
}
void add(int u,int v,int w)
{
    __add(u,v,w);
    __add(v,u,0);
}

bool bfs(int S,int T)
{
    memset(level,0x00,sizeof(level));
    queue<int> q;
    q.push(S);
    level[S]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=E[i].next)
        {
            int v=E[i].to;
            if(E[i].w==0||level[v]!=0)continue;
            level[v]=level[u]+1;
            q.push(v);
        }
    }
    return level[T];
}

int dfs(int u,int flow,int T)
{
    if(u==T||flow==0)return flow;
    int res=0;
    for(int i=cur[u];~i;cur[u]=i=E[i].next)
    {
        int v=E[i].to;
        if(level[v]==level[u]+1&&E[i].w!=0)
        {
            int f=dfs(v,std::min(flow,E[i].w),T);
            if(f!=0)
            {
                res+=f;
                flow-=f;
                E[i].w-=f;
                E[i^1].w+=f;
                if(flow==0)break;
            }
        }
    }
    return res;
}

int dinic(int S,int T)
{
    int res=0;
    while(bfs(S,T))
    {
        memcpy(cur,head,sizeof(head));
        res+=dfs(S,0x7fffffff,T);
    }
    return res;
}

int in_id(int x)
{
    return x;
}

int out_id(int x)
{
    return x+n;
}

int ans[N][N];

int main()
{
    memset(head,0xff,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        add(S,in_id(i),x);
        add(in_id(i),out_id(i),0x3fffffff);
    }
    int sum=0;
    for(int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        sum+=x;
        add(out_id(i),T,x);
    }
    for(int i=0;i<m;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(in_id(u),out_id(v),0x3fffffff);
        add(in_id(v),out_id(u),0x3fffffff);
    }
    if(dinic(S,T)!=sum)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int u=1;u<=n;++u)
    {
        for(int i=head[u];~i;i=E[i].next)
        {
            int v=E[i].to;
            if(v<=n)continue;
            if(v>n*2)continue;
            v-=n;
            ans[u][v]+=E[i].w0-E[i].w;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            printf("%d ",ans[i][j]);
        }
        putchar('\n');
    }
}