解题：WC 2007 石头剪刀布

要我们把边定向，最大化留下来的三元环数目......并不能直接做，考虑容斥，去掉不合法的数目。

那么三个点不成环当且仅当有一个点出度为2一个点入度为2，发现最终答案就是$C_n^3-\sum C_{outdeg}^2$，然后因为下凸函数和费用流相似的性质可以拆边费用流：

每个点向汇点连一坨流量为$1$费用为$0,1,2...$的边，然后再把每条边向连接的点连流量为$1$费用为$0$的边表示使得一个点出度加$1$，最后原点向每条边连流量为$1$费用为$0$的边

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=,inf=1e9;

 int p[N],noww[*M],goal[*M],flow[*M],cost[*M];

 int mflw[N],mcst[N],pren[N],pree[N],queu[N],degr[N];

 int game[N][N],gamx[N],gamy[N],numb[N]; queue<int> qs;

 int n,m,s,t,t1,t2,t3,t4,id,rd,cnt,num,ans;

 void link(int f,int t,int v,int c)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,flow[cnt]=v,cost[cnt]=c;

     noww[++cnt]=p[t],p[t]=cnt;

     goal[cnt]=f,flow[cnt]=,cost[cnt]=-c;

 }

 void Init(int st,int ed)

 {

     memset(mflw,0x3f,sizeof mflw);

     memset(mcst,0x3f,sizeof mcst);

     memset(queu,,sizeof queu),pren[ed]=-;

     qs.push(st),queu[st]=true,mcst[st]=;

 }

 bool SP(int st,int ed)

 {

     Init(st,ed);

     while(!qs.empty())

     {

         int tn=qs.front();

         qs.pop(),queu[tn]=false;

         for(int i=p[tn],g;i;i=noww[i])

             if(mcst[g=goal[i]]>mcst[tn]+cost[i]&&flow[i])

             {

                 pree[g]=i,pren[g]=tn;

                 mcst[g]=mcst[tn]+cost[i];

                 mflw[g]=min(mflw[tn],flow[i]);

                 if(!queu[g]) qs.push(g),queu[g]=true;

             }

     }

     return ~pren[ed];

 }

 void MCMF(int st,int ed)

 {

     while(SP(st,ed))

     {

         ans+=mflw[ed]*mcst[ed],id=ed;

         while(id!=st)

         {

             flow[pree[id]]-=mflw[ed];

             flow[pree[id]^]+=mflw[ed];

             id=pren[id];

         }

     }

 }

 int main()

 {

     scanf("%d",&n),cnt=,s=n+,num=t=n+;

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

         {

             scanf("%d",&game[i][j]);

             if(game[i][j]==)

             {

                 if(i<=j)

                 {

                     num++,gamx[num]=i,gamy[num]=j;

                     link(num,i,,),link(num,j,,);

                     numb[i]++,numb[j]++,link(s,num,,);

                 }

             }

             else degr[i]+=game[i][j];

         }

     for(int i=;i<=n;i++)

     {

         ans+=degr[i]*degr[i];

         for(int j=;j<=numb[i];j++)

             link(i,t,,*(degr[i]+j)-);

     }

     MCMF(s,t);

     printf("%d\n",n*(n-)*(n-)/-(ans-n*(n-)/)/);

     for(int i=t+;i<=num;i++)

     {

         int oppo,numx=gamx[i],numy=gamy[i];

         for(int j=p[i];j;j=noww[j])

             if(goal[j]!=s&&!flow[j])

                 {oppo=goal[j]; break;}

         game[numx][numy]=oppo==numx;

         game[numy][numx]=game[numx][numy]^;

     }

     for(int i=;i<=n;i++,puts(""))

         for(int j=;j<=n;j++)

             printf("%d ",game[i][j]);

     return ;

 }

巴特西

解题：WC 2007 石头剪刀布

最新文章

热门文章