输出的时候发现不会对原来的矩阵排序,只好重新搞了一储存边的一维数组,然后排序。
- #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,sizeof(p));
- memset(a,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,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\n");
- else
- {
- int tp=0;
- printf("YES\n");
- 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\n",g[i].f);
- }
- }
- int main()
- {
- int _,i,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;
- }