直接求不好求引入未知數，考慮采用補集轉化

對于一次非剪刀石頭布的情況，定是一個人贏了另兩個人

若知道一個人共贏了多少人，那么就貢獻了n*(n-1)/2種不同的情況

更一般的，一個人如果多贏了一個人，他的新增的貢獻就是他當前沒有加上這個人時已經贏了的人

費用流。

st->比賽->人->ed，費用是遞增的，對于人拆點，一條一條不同費用的連

?

我真是震驚了暴力跑得比費用流還快。。。ORZ bzoj14年就踩崩這題的test_tset在discuss教我迭代

ta沒回我之前我腦洞大開寫了一發模擬退火，效果極差，我想了一手隨機處理2的順序直接貪心，發現和正確答案已經很接近了，導致退火完全跳不出來。。。

然后這個大佬的做法：

實踐中這個做法比我的網絡流快了1倍不止（或許是修正主義在作祟？？？）

?

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int inf=(1<<30);struct node {int x,y,c,d,next; }a[410000];int len,last[11000]; void ins(int x,int y,int c,int d) {len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;a[len].next=last[x];last[x]=len;len++;a[len].x=y;a[len].y=x;a[len].c=0;a[len].d=-d;a[len].next=last[y];last[y]=len; }int st,ed; int pre[11000],c[11000],d[11000],ans; int list[11000];bool v[11000]; bool spfa() {memset(d,63,sizeof(d));d[st]=0;c[st]=inf;memset(v,false,sizeof(v));v[st]=true;int head=1,tail=2;list[1]=st;while(head!=tail){int x=list[head];for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(a[k].c>0&&d[y]>d[x]+a[k].d){d[y]=d[x]+a[k].d;c[y]=min(a[k].c,c[x]);pre[y]=k;if(v[y]==false){v[y]=true;list[tail]=y;tail++;if(tail==10500)tail=1;}}}v[x]=false;head++;if(head==10500)head=1;}if(d[ed]==d[0])return false;else{int y=ed;ans+=c[ed]*d[ed];while(y!=st){int k=pre[y];a[k].c-=c[ed];a[k^1].c+=c[ed];y=a[k].x;}return true;} }int mp[110][110],px[11000],py[11000]; int hw[110],hl[110]; int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);int n,z=0,sum=0;scanf("%d",&n);len=1; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&mp[i][j]);if(i>=j)continue;if(mp[i][j]==1)sum+=hw[i],hw[i]++,hl[j]++;else if(mp[i][j]==0)sum+=hw[j],hw[j]++,hl[i]++;else z++,px[z]=i,py[z]=j,ins(2*n+z,i,1,0), ins(2*n+z,j,1,0);}st=2*n+z+1,ed=2*n+z+2;for(int i=1;i<=z;i++)ins(st,2*n+i,1,0);for(int i=1;i<=n;i++){for(int j=hw[i]+1;j<=n-hl[i];j++)ins(i,i+n,1,j-1);ins(i+n,ed,inf,0);}while(spfa());printf("%d\n",n*(n-1)/2*(n-2)/3-(ans+sum));int x,y,g;for(int i=2;i<=len;i+=2)if(a[i].x>2*n&&a[i].x<=2*n+z){g=a[i].x-2*n;if(px[g]==a[i].y)x=px[g],y=py[g];else x=py[g],y=px[g];mp[x][y]=a[i].c^1;}for(int i=1;i<=n;i++){for(int j=1;j<n;j++)printf("%d ",mp[i][j]);printf("%d\n",mp[i][n]);}return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/10265258.html

總結

以上是生活随笔為你收集整理的bzoj2597: [Wc2007]剪刀石头布的全部內容，希望文章能夠幫你解決所遇到的問題。

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