zoj 2314 Reactor Cooling上下界のネットワーク最大ストリーム

8554 ワード

出力時に元のマトリクスをソートしないことに気づき,エッジを格納する1次元配列を再作成してソートするしかなかった.
#include<bits/stdc++.h>
using namespace std;
const int N=256;
const int inf=0x7fffffff;

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

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

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

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