sort貌似不能给2维数组排序呢？ 改成qsort就好了，这里的构图方法和周源的论文里的类似
题目是求一个有上下界网络中的无源汇的可行流。
构造伴随网络方法如下：
新增两个顶点VS VT 对原网络每个顶点算其D(u)的值，其中D(u)为顶点u发出的所有弧的流量下界和进入u的所有弧的流量下界之差，当D(u)>0，则新增一条弧<u,VT>，容量为D(u),当D(u)<0时，则新增一条弧<VS,u>，容量-D(u)，D(u)=0不加弧，原网络的每条弧仍保留，容量改为c(u,v)-b(u,v)。
这个是自己敲的，无优化 ， 主要是为了理解accompany network,下面又给出了优化的代码，效率不是一个数量级的。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> //这段代码很垃圾 不能拿来当模板 要修改 修改 using namespace std; #define min(a,b) (a)>(b)?(b):(a) const int Inf=0x3f3f3f3f;//与memset全设63是等价的 const int maxn=205; int n,m; int source=0,sink; struct Arc { int b,c,f,No_; //Arc(int bb,int cc,int ff,int nn)b(bb),c(cc),f(ff),No_(nn){}; }; Arc edge[maxn][maxn]; Arc accedge[maxn][maxn]; int flag[maxn]; int prev[maxn]; int alpha[maxn]; int queue[maxn]; int v,qhead,qrear; int cmp (const void *a,const void *b) { return ((Arc *)a)->No_-((Arc*)b)->No_; } void ford (Arc network[][maxn],int s,int t) { int i,j; while (1) { memset(flag,-1,sizeof(flag)); memset(prev,sizeof(prev)); flag[s]=0 ; prev [s]=0 ; alpha[s]=Inf; qhead=0; queue[0]=s;qrear=1; while (qhead<qrear && flag[t]==-1) { v=queue [qhead]; qhead++; for (i=s ; i<=t ; ++i) { if(flag[i]==-1) { if(network[v][i].c<Inf && network[v][i].f<network[v][i].c) { flag[i]=0 ; prev[i]=v ; alpha[i]=min(alpha[v],network[v][i].c-network[v][i].f); queue[qrear]=i;qrear++; } else if(network[i][v].c<Inf && network[i][v].f> network[i][v].b) { flag[i]=0 ; prev[i]=-v; alpha[i]=min(alpha[v],network[i][v].f-network[i][v].b); queue[qrear]=i;qrear++; } } } flag[v]=1; } if(flag[t]==-1 || alpha[t]==0)break; int k1=t,k2=fabs(prev[k1]),a=alpha[t]; while (1) { if(network[k2][k1].f<Inf) network[k2][k1].f+=a; else network[k1][k2].f-=a; if(k2==s)break; k1=k2 ; k2=fabs(prev[k2]); } } } void accompany ()//构造伴随网络 { int i,j; memcpy(accedge,edge,sizeof(edge)); for (i=1 ; i<=n ; i++) { int sum1=0,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,n+1); bool fflag=1; for (i=0 ; i<=n+1 ; ++i)//若 { if(accedge[0][i].c!=Inf && accedge[0][i].f!=accedge[0][i].c)fflag=0; } if(fflag==0) { printf("NO\n");return ; } 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; } } printf("YES\n"); qsort(edge,205*205,sizeof(Arc),cmp);//不知道为什么 用sort就不能过 for ( i=0 ; i<m ; ++i ) printf("%d\n",edge[i/m][i%m].f); } int main () { int u,v,b; int T; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); memset (edge,63,sizeof(edge)); for (int i=0 ; 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; }
省去了结构体，直接对伴随网络的残留网络进行构造
模板中的res是残留网络 ，对定义要熟练巩固。
#include <cstdio> #include <string.h> #define min(a,b) ((a)>(b))?(b):(a) using namespace std ; const int maxn=210; const int maxm=40005; const int Inf=0x4fffffff; int cap[maxn][maxn];//原网络 int bflow[maxn][maxn];//下限 int dist[maxn],gap[maxn]; int res[maxn][maxn];//伴随网络的残留网络 int x[maxm],y[maxm]; int n,m; int dfs (int p,int limit=Inf) { if(p==n)return limit; for (int i=0 ; i<=n ; ++i) { if(dist[p]==dist[i]+1 && res[p][i]>0) { int t=dfs(i,min(limit,res[p][i])); if(t<0)return t; if(t>0) { res[p][i]-=t;//残留网络 res[i][p]+=t;//残留网络的反向弧存的就是当前弧的正向流量 return t; } } } int tmp=n+1 ; for (int i=0 ; i<=n ; ++i) if(res[p][i]>0) tmp=min(tmp,dist[i]+1); /*printf("dist[p]=%d dist0=%d tmp=%d\n",dist[p],dist[0],tmp); printf("gap="); for (int i=0 ; i<n ; i++)printf("%d ",gap[i]); puts("");*/ if(--gap[dist[p]]==0 || dist[0]>n)return -1; ++gap[dist[p]=tmp]; return 0; } int SAP() { gap[0]=n+1; int f = 0,t=0; while (~(t=dfs(0))) f+=t; //printf("%d\n",t); return f; } void init () { memset (cap,sizeof(cap)); memset (res,sizeof(res)); memset (dist,sizeof(dist)); memset (gap,sizeof(gap)); memset (bflow,sizeof(bflow)); } void accompany () { int i,j,sum1,sum2; n++;//增加汇点 for (i=1 ; i<n ; ++i) { sum1=sum2=0; for (j=1 ; j<n ; ++j) { if(bflow[i][j]>0)sum1+=bflow[i][j]; if(bflow[j][i]>0)sum2+=bflow[j][i]; } int tmp=sum2-sum1; tmp>0?(res[0][i]=tmp):res[i][n]=-tmp; } SAP(); bool flag=1; for (i=0 ; i<=n ; ++i) { //printf("%d %d %d %d %d\n",res[0][i],res[1][i],res[2][i],res[3][i],res[4][i]); if(res[0][i]!=0)flag=0; } if(!flag){printf("NO\n"); return ;} printf("YES\n"); for (i=0 ; i<m ; ++i) printf("%d\n",cap[x[i]][y[i]]-res[x[i]][y[i]]);//printf("%d\n",res[y[i]][x[i]]+bflow[x[i]][y[i]]);这个也可以 } int main () { int cas,i,u,b,sum; //freopen ("in.txt","r",stdin); //freopen ("out.txt","w",stdout); scanf("%d",&cas); while (cas--) { init(); scanf("%d%d",&m); for (i=0 ; i<m ; i++) { scanf("%d%d%d%d",x+i,y+i,&c); cap[x[i]][y[i]]=c; res[x[i]][y[i]]=c-b; bflow[x[i]][y[i]]=b; } accompany(); } return 0; }
