题面：
有N个人参加一场比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有N*(N-1)/2场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。
剪刀石头布情况，即无序三元组(A, B, C)，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。
分析：
把题意转化一下，就是给定了一张有向完全图的残本，剩下的边你可以任意安排，求出现最多的三元环数量。
我们可以用一下小小的容斥，假如我们任选三个点，方案数是C(n,3)，我们就找出最少失去的三元环数量，就可以给出这个题的答案了。
根据《一眼看出法》，我们可以了解，假如一个点x的入度（以下简称in[x]）为w，那么它会使整个图失去的三元环数量为C(w,2)。
即：如果一个点的入度增加1，会使三元环数量减少in[x]-1这么多。所以我们需要尽量保证不会出现某个点入度特别多，换句话说就是尽量让入度平均。（这大概就是题解中说的凸函数的性质？？？）
所以，我们将失去的三元环作费用，跑费用流。
对于未定向的边，我们将其抽象成点（这里原图中的点也被抽象成点）
我们由源点S向每条未定向的边对应的点连边，容量为1费用为0；
对于每条被我们建成点的边，我们从这个点向这条边连通的两个点连边，容量为1，费用为0，表示这条边会给其中一个点带来入度加一的贡献。
对于每个原图上的节点x，我们想汇点T连接若干条边，容量都为1，费用分别为in[x], in[x]+1, in[x]+2,…,n-2（表示每增加1个单位的流量，就会带来这么多三元环的毁灭。想想为什么最大是n-2？）
之后定向方案，看边对应的点哪条出边满流即可！
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100005,inf=0x3f3f3f3f;int f[N]; 4 struct node{int y,z,f,nxt;}e[N*16];int lst[N]; 5 int n,S,T,tot,g[105][105],dg[N],tmp[N],X[N],Y[N]; 6 int h[N],c=1,d[N],vis[N],pre[N],ans;queue<int>q; 7 void add(int x,int y,int l,int z){ 8 e[++c]=(node){y,z,l,h[x]};h[x]=c; 9 e[++c]=(node){x,-z,0,h[y]};h[y]=c; 10 } bool spfa(){ 11 for(int i=S;i<=T;i++) pre[i]=-1, 12 f[i]=inf,lst[i]=vis[i]=0,d[i]=inf; 13 q.push(S);d[S]=0;pre[S]=0; 14 while(!q.empty()){ 15 int x=q.front();q.pop();vis[x]=0; 16 for(int i=h[x],y;~i;i=e[i].nxt) 17 if(d[y=e[i].y]>d[x]+e[i].z&&e[i].f){ 18 d[y]=d[x]+e[i].z;pre[y]=x;lst[y]=i; 19 f[y]=min(f[x],e[i].f); 20 if(!vis[y]) vis[y]=1,q.push(y); 21 } 22 } return pre[T]!=-1; 23 } void solve(){ 24 while(spfa()){ 25 ans+=d[T]*f[T];int x=T; 26 while(x) e[lst[x]].f-=f[T], 27 e[lst[x]^1].f+=f[T],x=pre[x]; 28 } return ; 29 } int main(){ 30 memset(h,-1,sizeof(h)); 31 scanf("%d",&n);S=0,tot=n; 32 for(int i=1;i<=n;i++) 33 for(int j=1;j<=n;j++){ 34 scanf("%d",&g[i][j]); 35 if(g[i][j]==2){ 36 if(i>j) continue; 37 X[++tot]=i,Y[tot]=j; 38 add(S,tot,1,0); 39 add(tot,i,1,0); 40 add(tot,j,1,0); 41 tmp[i]++;tmp[j]++; 42 } else dg[i]+=g[i][j]; 43 } T=++tot;for(int i=1;i<=n;i++){ 44 ans+=(dg[i]*dg[i]-dg[i])/2; 45 for(int j=dg[i]+1;j<n;j++) 46 add(i,T,1,j-1); 47 } solve();int tt=n*(n-1)*(n-2)/6; 48 printf("%d ",tt-ans); 49 for(int i=n+1,v;i<tot;i++){ 50 for(int p=h[i];~p;p=e[p].nxt) 51 if(e[p].y!=S&&!e[p].f) 52 {v=e[p].y;break;} 53 if(v==X[i]) g[X[i]][Y[i]]=1, 54 g[Y[i]][X[i]]=0; 55 else g[X[i]][Y[i]]=0,g[Y[i]][X[i]]=1; 56 } for(int i=1;i<=n;i++,puts("")) 57 for(int j=1;j<=n;j++) 58 printf("%d ",g[i][j]);return 0; 59 }