【WC2007】剪刀石头布 | Mrsrz's blog

费用流

题目大意：

给定一张竞赛图，有些边已经定向了，现在要给剩下的边定向，使得图中的三元环个数最多。求最多个数以及方案。

题解：

如果三个点之间的边不构成三元环，那么必然有一个点向另外两个点都有连边。我们把这个“不是三元环”的贡献，计算到出度为 $2$ 的那个点上。

考虑用总三元组个数减去不是三元环的个数。那么要求不是三元环的个数最少。

由于是竞赛图，任意三点都可能成环，所以总数为 $\binom n3$。

考虑一个点的出度如果为 $d$，那么任选两条出边，都会形成一个“不是三元环”的贡献。所以它的贡献为 $\frac{d(d-1)}{2}$。

然后我们知道，$\frac{d(d-1)}{2}=1+2+3+\dots+d$。

可以考虑费用流，每一条未定向的边，会选择流到两个点中的一个。对每个点，向汇点连容量为 $1$，费用为 $d_i,d_i+1,d_i+2,\dots,n$ 的边各一条，其中 $d_i$ 表示原有出度。

然后跑最小费用最大流。由于保证在同样流量的情况下费用最小，因此对每个点，都会先挑贡献小的边，那么就可以保证其贡献是正确的了。

满流下的费用就是最少的“不是三元环”的个数。

建出来的图每条边的容量均为 $1$，用 Dinic 费用流会非常快。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N=11005,M=200005,S=0;
int head[N],cnt=1,deg[105],T,ans,iter[N],dis[N],n,out[105][105];
bool vis[N];
vector<pair<int,int> >vec;
struct edge{
    int to,nxt,cap,cost;
}e[M<<1];
inline void addedge(int u,int v,int cap,int cost){
    e[++cnt]=(edge){v,head[u],cap,cost},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0,-cost},head[v]=cnt;
}
queue<int>q;
int dfs(int u,int f){
    if(!f||u==T)return f;
    vis[u]=1;
    int ret=0;
    for(int&i=iter[u];i;i=e[i].nxt)
        if(e[i].cap&&!vis[e[i].to]&&dis[e[i].to]==dis[u]+e[i].cost){
            int d=dfs(e[i].to,min(f,e[i].cap));
            e[i].cap-=d,e[i^1].cap+=d,ret+=d,f-=d;
            if(!f)break;
        }
    vis[u]=0;
    return ret;
}
bool MCMF(int&flow,int&cost){
    memset(dis,0x3f,(T+2)<<2);
    dis[S]=0;
    memset(vis,0,sizeof(bool)*(T+2));
    for(q.push(S);!q.empty();){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].cap&&dis[e[i].to]>dis[u]+e[i].cost){
                dis[e[i].to]=dis[u]+e[i].cost;
                if(!vis[e[i].to])vis[e[i].to]=1,q.push(e[i].to);
            }
    }
    if(dis[T]>1e9)return 0;
    memcpy(iter,head,(T+2)<<2);
    int dlt=dfs(S,0x3fffffff);
    flow+=dlt,cost+=dis[T]*dlt;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            int&x=out[i][j];
            cin>>x;
            if(i<j)
                switch(x){
                    case 1:++deg[i];break;
                    case 0:++deg[j];break;
                    case 2:vec.push_back(make_pair(i,j));
                }
        }
    }
    T=n*n+n*2;
    ans=n*(n-1)*(n-2)/6;
    for(int d=1;d<=n;++d){
        ans-=deg[d]*(deg[d]-1)>>1;
        for(int i=deg[d];i<=n;++i)addedge(d,T,1,i);
    }
    int nod=n;
    for(int i=0;i<vec.size();++i){
        int u=vec[i].first,v=vec[i].second;
        ++nod;
        addedge(S,nod,1,0);
        addedge(nod,u,1,0);
        addedge(nod,v,1,0);
    }
    int flow=0,cost=0;
    while(MCMF(flow,cost));
    ans-=cost;
    cout<<ans<<'\n';
    for(int i=0;i<vec.size();++i){
        int to_u=head[n+1+i],to_v=e[to_u].nxt,u=e[to_u].to,v=e[to_v].to;
        if(e[to_u].cap==0)out[u][v]=1,out[v][u]=0;else out[v][u]=1,out[u][v]=0;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            cout<<out[i][j]<<" \n"[j==n];
    return 0;
}