BZOJ2597:[Wc2007]剪刀石头布 补集转化+费用流

思路:注意到三元环不好求,于是转化为所有三元组的数量减去不能形成环的三元组的数量.

我们令\(i\)输给\(j\),便有一条\(i\rightarrow{j}\)的有向边.

考虑不能形成三元环的三元组,则三个点之中必然有一个点入度为\(2\).

那么不能形成环的所有三元组的数量就等于:

\[add=\sum_{i=1}^{n}C_{indegree_{i}}^{2}\]

这意味着:对于所有入边,我们随意找出两个,都显然可以形成一个不能形成环的三元组.而且这样计算显然是不重不漏的.

考虑我们的答案:

\[ans=C_{n}^{3}-add=C_{n}^{3}-\sum_{i=1}^{n}\frac{indegree_{i}(indegree_{i}-1)}{2}\]

那么我们事实上是要最小化后面减去的东西.

我们对于每一场结果未知的比赛分配胜负,若令一个人取胜,那么其入度\(+1\),就会带来总答案的增加,我们发现每一次增广从某个节点通过的费用是单调不减的,于是拆边作费用流即可.

输出方案也就随便搞搞.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 110
int G[N][N];
  
queue<int>q;
struct Solver{
    int head[5100],next[50010],end[50010],flow[50010],cost[50010],ind;
    int d[5100],used[5100],slack[5100],id;bool inq[5100];
    inline void reset(){ind=0,id=1,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q++]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline void spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;
            for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j];
                if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }for(int i=S;i<=T;++i)d[i]=d[T]-d[i];
    }
    inline bool Newlabel(int S,int T){
        int Min=INF;for(int i=S;i<=T;++i)if(used[i]!=id&&slack[i]<Min)Min=slack[i];
        if(Min==INF)return 0;
        for(int i=S;i<=T;++i)if(used[i]==id)used[i]=-1,d[i]+=Min;return 1;
    }
    int Getflow(int p,int T,int maxflow){
        if(p==T)return maxflow;
        used[p]=id;
        for(int j=head[p];j!=-1;j=next[j]){
            if(flow[j]&&used[end[j]]!=id&&d[end[j]]+cost[j]==d[p]){
                int to=Getflow(end[j],T,maxflow<flow[j]?maxflow:flow[j]);if(to){flow[j]-=to,flow[j^1]+=to;return to;}
            }else if(flow[j])slack[end[j]]=min(slack[end[j]],d[end[j]]+cost[j]-d[p]);
        }return 0;
    }
    int Mincost(int S,int T){
        int res(0),get;spfa(S,T);
        do{
            memset(slack,0x3f,sizeof slack);
            while((get=Getflow(S,T,INF)))res+=d[S]*get,++id;
        }while(Newlabel(S,T));return res;
    }
}InuyashaKikyou;
  
#define Make InuyashaKikyou.make
int win[N],lose[N];
int main(){
    int n;scanf("%d",&n);
    register int i,j;for(i=1;i<=n;++i)for(j=1;j<=n;++j)scanf("%d",&G[i][j]);
    int id=0,t=0;for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(G[i][j]==2)++id;
    int S=0,T=n+id+1;
    InuyashaKikyou.reset();
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j){
        if(G[i][j]==1)++win[i],++lose[j];else if(G[i][j]==0)++win[j],++lose[i];
        else Make(S,++t,1,0),Make(t,id+i,1,0),Make(t,id+j,1,0);
    }
    int nowcnt=0;
    for(i=1;i<=n;++i){
        int last=n-1-win[i]-lose[i];nowcnt+=win[i]*(win[i]-1)/2;
        while(last--)Make(id+i,T,1,win[i]++);
    }
    nowcnt+=InuyashaKikyou.Mincost(S,T);
    printf("%d\n",n*(n-1)*(n-2)/6-nowcnt);
  
    int to[2],last[2];
    for(i=1;i<=id;++i){
        int cnt=0;
        for(j=InuyashaKikyou.head[i];j!=-1;j=InuyashaKikyou.next[j]){
            if(InuyashaKikyou.end[j]>id)to[cnt]=InuyashaKikyou.end[j]-id,last[cnt++]=InuyashaKikyou.flow[j];
        }
        if(last[0]==0&&last[1]==1)G[to[0]][to[1]]=1,G[to[1]][to[0]]=0;
        else G[to[1]][to[0]]=1,G[to[0]][to[1]]=0;
    }
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j)printf("%d ",G[i][j]);puts("");
    }
    return 0;
}