输出的时候发现不会对原来的矩阵排序,只好重新搞了一储存边的一维数组,然后排序。
#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@;
}