zoj 2314 Reactor Cooling 有上下界的网络最大流

前端之家收集整理的这篇文章主要介绍了zoj 2314 Reactor Cooling 有上下界的网络最大流前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

输出的时候发现不会对原来的矩阵排序,只好重新搞了一储存边的一维数组,然后排序。

#include<bits/stdc++.h>@H_301_5@
using@H_301_5@ namespace@H_301_5@ std@H_301_5@;
const@H_301_5@ int@H_301_5@ N=256@H_301_5@;
const@H_301_5@ int@H_301_5@ inf=0x7fffffff@H_301_5@;

struct@H_301_5@ type
{
    int@H_301_5@ b,c,f;
    int@H_301_5@ no;
};
struct@H_301_5@ node
{
    int@H_301_5@ no,f;
}g[20000@H_301_5@+5@H_301_5@];
int@H_301_5@ cmp(node a,node b)
{
    return@H_301_5@ a.no<b.no;
}

type Edge[N][N];
type AccEdge[N][N];
int@H_301_5@ n,m;
int@H_301_5@ flag[N],p[N],a[N];

void@H_301_5@ Ford(type network[][N],int@H_301_5@ s,int@H_301_5@ t)
{
    int@H_301_5@ i,j,u;
    while@H_301_5@(1@H_301_5@)
    {
        memset@H_301_5@(flag,0xff@H_301_5@,sizeof@H_301_5@(flag));
        memset@H_301_5@(p,sizeof@H_301_5@(p));
        memset@H_301_5@(a,sizeof@H_301_5@(a));
        flag[s]=0@H_301_5@;
        p[s]=0@H_301_5@;
        a[s]=inf;
        queue@H_301_5@<int@H_301_5@>@H_301_5@Q;
        Q.push(s);
        while@H_301_5@(!Q.empty()&&flag[t]==-1@H_301_5@)
        {
            u=Q.front();
            Q.pop();
            for@H_301_5@(i=s; i<=t; i++)
            {
                if@H_301_5@(flag[i]!=-1@H_301_5@) continue@H_301_5@;
                if@H_301_5@(network[u][i].c<inf&&network[u][i].f<network[u][i].c)
                {
                    flag[i]=0@H_301_5@;
                    p[i]=u;
                    a[i]=min(a[u],network[u][i].c-network[u][i].f);
                    Q.push(i);
                }
                else@H_301_5@ if@H_301_5@(network[i][u].c<inf&&network[i][u].f>network[i][u].b)
                {
                    flag[i]=0@H_301_5@;
                    p[i]=u;
                    a[i]=min(a[u],network[i][u].f-network[i][u].b);
                    Q.push(i);
                }
            }
            flag[u]=1@H_301_5@;
        }
        if@H_301_5@(flag[t]==-1@H_301_5@||a[t]==0@H_301_5@) break@H_301_5@;
        int@H_301_5@ k1=t,k2=p[k1];
        while@H_301_5@(1@H_301_5@)
        {
            if@H_301_5@(network[k2][k1].f<inf)
                network[k2][k1].f=network[k2][k1].f+a[t];
            else@H_301_5@
                network[k1][k2].f=network[k1][k2].f-a[t];
            if@H_301_5@(k2==s) break@H_301_5@;
            k1=k2;
            k2=p[k1];
        }
    }
}

void@H_301_5@ accompany()
{
    memcpy@H_301_5@(AccEdge,Edge,sizeof@H_301_5@(Edge));
    int@H_301_5@ i,sum1,sum2;
    for@H_301_5@(i=1@H_301_5@; i<=n; i++)
    {
        sum1=sum2=0@H_301_5@;
        for@H_301_5@(j=1@H_301_5@; j<=n; j++)
        {
            if@H_301_5@(AccEdge[i][j].b!=inf) sum1+=AccEdge[i][j].b;
            if@H_301_5@(AccEdge[j][i].b!=inf) sum2+=AccEdge[j][i].b;
        }
        if@H_301_5@(sum2>sum1)
            AccEdge[0@H_301_5@][i].c=sum2-sum1,AccEdge[0@H_301_5@][i].b=AccEdge[0@H_301_5@][i].f=0@H_301_5@;
        else@H_301_5@
            AccEdge[i][n+1@H_301_5@].c=sum1-sum2,AccEdge[i][n+1@H_301_5@].b=AccEdge[i][n+1@H_301_5@].f=0@H_301_5@;
    }
    for@H_301_5@(i=1@H_301_5@; i<=n; i++)
        for@H_301_5@(j=1@H_301_5@; j<=n; j++)
            if@H_301_5@(AccEdge[i][j].c!=inf)
            {
                AccEdge[i][j].c=AccEdge[i][j].c-AccEdge[i][j].b;
                AccEdge[i][j].b=0@H_301_5@;
            }
    Ford(AccEdge,0@H_301_5@,n+1@H_301_5@);
    bool@H_301_5@ ok=1@H_301_5@;
    for@H_301_5@(i=0@H_301_5@; i<=n+1@H_301_5@; i++)
    {
        if@H_301_5@(AccEdge[0@H_301_5@][i].c!=inf&&AccEdge[0@H_301_5@][i].f!=AccEdge[0@H_301_5@][i].c)
            ok=0@H_301_5@;
    }
    if@H_301_5@(!ok) printf@H_301_5@("NO\n"@H_301_5@);
    else@H_301_5@
    {
        int@H_301_5@ tp=0@H_301_5@;
        printf@H_301_5@("YES\n"@H_301_5@);
        for@H_301_5@(i=1@H_301_5@; i<=n; i++)
            for@H_301_5@(j=1@H_301_5@; j<=n; j++)
                if@H_301_5@(Edge[i][j].c!=inf)
                   {
                        Edge[i][j].f=AccEdge[i][j].f+Edge[i][j].b;
                        g[tp].f=Edge[i][j].f;
                        g[tp].no=Edge[i][j].no;
                        tp++;
                    }
       sort(g,g+tp,cmp);
       for@H_301_5@(i=0@H_301_5@;i<tp;i++)
        printf@H_301_5@("%d\n"@H_301_5@,g[i].f);
    }
}
int@H_301_5@ main()
{
    int@H_301_5@ _,i,u,v,b,c;
    scanf@H_301_5@("%d"@H_301_5@,&_);
    while@H_301_5@(_--)
    {
        scanf@H_301_5@("%d%d"@H_301_5@,&n,&m);
        for@H_301_5@(i=0@H_301_5@; i<n+2@H_301_5@; i++)
            for@H_301_5@(j=0@H_301_5@; j<n+2@H_301_5@; j++)
                Edge[i][j].c=Edge[i][j].b=Edge[i][j].f=Edge[i][j].no=inf;
        for@H_301_5@(i=1@H_301_5@; i<=m; i++)
        {
            scanf@H_301_5@("%d%d%d%d"@H_301_5@,&u,&v,&b,&c);
            Edge[u][v].b=b;
            Edge[u][v].c=c;
            Edge[u][v].f=0@H_301_5@;
            Edge[u][v].no=i;
        }
        accompany();
    }
    return@H_301_5@ 0@H_301_5@;
}

猜你在找的React相关文章