100%的数据中，N≤ 100。
题解：
Orz PoPoQQQ 补集转化太神了
http://blog.csdn.net/PoPoQQQ/article/details/42424307
code：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 11000 7 #define maxm 60000 8 #define inf 1061109567 9 using namespace std; 10 char ch; 11 bool ok; 12 void read(int &x){ 13 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch==‘-‘) ok=1; 14 for (x=0;isdigit(ch);x=x*10+ch-‘0‘,ch=getchar()); 15 if (ok) x=-x; 16 } 17 int n,win[105],lose[105],g[105][105],sum; 18 struct zkw_costflow{ 19 int s,t,tot,now[maxn],son[maxm],pre[maxm],val[maxm],cost[maxm]; 20 int dis[maxn],tmp,totflow,totcost; 21 bool bo[maxn]; 22 void init(){s=0,t=n*n+n+1,tot=1,memset(now,0,sizeof(now));} 23 void put(int a,int b,int c,int d){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c,cost[tot]=d;} 24 void add(int a,int b,int c,int d){put(a,b,c,d),put(b,a,0,-d);} 25 int dfs(int u,int rest,int totval){ 26 bo[u]=1; 27 if (u==t){totcost+=rest*totval;return rest;} 28 int ans=0; 29 for (int p=now[u],v=son[p];p&&rest;p=pre[p],v=son[p]) 30 if (val[p]&&!bo[v]&&dis[v]==dis[u]+cost[p]){ 31 int d=dfs(v,min(rest,val[p]),totval+cost[p]); 32 val[p]-=d,val[p^1]+=d,ans+=d,rest-=d; 33 } 34 return ans; 35 } 36 bool relax(){ 37 int d=inf; 38 for (int u=s;u<=t;u++) if (bo[u]) 39 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) 40 if (val[p]&&!bo[v]) d=min(d,cost[p]+dis[u]-dis[v]); 41 if (d==inf) return false; 42 for (int u=s;u<=t;u++) if (!bo[u]) dis[u]+=d; 43 return true; 44 } 45 void work(){ 46 memset(dis,0,sizeof(dis)),totflow=totcost=0; 47 do{ 48 do{ 49 memset(bo,0,sizeof(bo)); 50 tmp=dfs(s,inf,0),totflow+=tmp; 51 }while (tmp); 52 }while (relax()); 53 } 54 void solve(){ 55 for (int u=1;u<=n*n;u++) if (now[u]){ 56 int p1=now[u],v1=son[p1]-n*n,p2=pre[p1],v2=son[p2]-n*n; 57 if (!val[p1]) g[v1][v2]=1,g[v2][v1]=0; 58 else g[v2][v1]=1,g[v1][v2]=0; 59 } 60 } 61 }f; 62 int main(){ 63 read(n),f.init(); 64 for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ 65 read(g[i][j]); 66 if (g[i][j]==1) win[i]++; else if (g[i][j]==0) lose[i]++; 67 } 68 for (int i=1;i<=n;i++) sum+=win[i]*(win[i]-1)/2; 69 for (int i=1;i<=n;i++) for (int j=win[i];j<n-lose[i];j++) f.add(n*n+i,f.t,1,j); 70 for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (g[i][j]==2) 71 f.add(f.s,(i-1)*n+j,1,0),f.add((i-1)*n+j,n*n+i,1,0),f.add((i-1)*n+j,n*n+j,1,0); 72 f.work(); 73 printf("%d\n",n*(n-1)*(n-2)/6-f.totcost-sum); 74 f.solve(); 75 for (int i=1;i<=n;i++,puts("")) for (int j=1;j<=n;j++) printf("%d ",g[i][j]); 76 return 0; 77 }
原文：http://www.cnblogs.com/chenyushuo/p/5141757.html