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;
}