題面：

　　有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\n",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 } 費用流

?

轉載于:https://www.cnblogs.com/Alan-Luo/p/10250962.html

總結

以上是生活随笔為你收集整理的WC2007 石头剪刀布 数学+最小费用最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。