题解 P4249 【[WC2007]剪刀石头布】

Nemlit

2019-01-28 22:01:27

Solution

一句话题意:给定一张图,每两点之间有一条有向边或无向边,把所有无向边定向,使图中三元环个数尽量多 因为原图是一个完全图,假设图中任意三点都能构成三元环,那么途中三元环的个数为:$\binom{n}{3}$。 那么如果一个三元组不是三元环,那么有一个点的出度为2。 我们假设一个点的出度为d,那么对于这个点,三元环会减少$\frac{d (d-1)}{2}$ 所以三元环的数量为:$\binom{n}{3}- \sum_{i=1}^n\binom{d[i]}{2}=\binom{n}{3}- \sum_{i=1}^n\frac{d[i] (d[i]-1)}{2}$ 所以我们要最小化:$ \sum_{i=1}^n\frac{d[i] (d[i]-1)}{2}$的值。 怎么做呢? 如果我们对于一条无向边,可能让u出度+1,也可能让v出度+1,非黑即白,所以我们可以考虑费用流。 观察柿子$\frac{d[i] (d[i]-1)}{2}$,容(hen)易(nan)想到小学等差数列求和公式,于是我们可以将一个点的贡献看成$(0+1+2+3+……+d[i]-1)$ 把每一条边看成一个点,从源点向每条边连一条容量为1,费用为0的边。 对于一条无向边,往u,v分别建一条容量为1,费用为0的边。 有向边则把边和v建一条容量为1,费用为0的边。 每个点向汇点连n条容量为1,费用为0-(n-1)递增的边,表示上面的等差数列(可以表示出任何出度的情况) 最后就是费用流的板子了 代码如下: ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define inf 123456789 #define debug printf("Now is Line : %d\n",__LINE__) il int read() { re int x=0,f=1; re char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x*f; } #define maxn 105 #define maxm 105*105 struct edge { int v,w,val,next; }e[maxm<<3]; int n,a[maxn][maxn],S,T,maxflow,cost,vis[maxm],dis[maxm],head[maxm],cnt=1,pa; il void add(int u,int v,int val,int w) { e[++cnt]=(edge){v,w,val,head[u]}; head[u]=cnt; e[++cnt]=(edge){u,-w,0,head[v]}; head[v]=cnt; } queue<int>q; il bool spfa() { memset(vis,0,sizeof(vis)); memset(dis,127,sizeof(dis)); dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(re int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]>dis[u]+e[i].w&&e[i].val>0) { dis[v]=dis[u]+e[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[T]!=2139062143; } il int dfs(int u,int mi) { if(u==T) { vis[T]=1; return mi; } vis[u]=1; int use=0; for(re int i=head[u];i;i=e[i].next) { int v=e[i].v; if((!vis[v]||v==T)&&e[i].val>0&&dis[v]==dis[u]+e[i].w) { int low=dfs(v,min(mi-use,e[i].val)); if(low>0) { cost+=low*e[i].w; e[i].val-=low; e[i^1].val+=low; use+=low; } } } return use; } il void dinic() { while(spfa()) { vis[T]=1; while(vis[T]) { memset(vis,0,sizeof(vis)); dfs(S,inf); } } int ans=((n-1)*(n-2)*n)/6; ans-=cost; printf("%d\n",ans); } int main() { n=read(); T=n*n+n+1; for(re int i=1;i<=n;++i) { for(re int j=1;j<=n;++j) { a[i][j]=read(); if(i>=j) continue; if(a[i][j]==2) { add(S,(i-1)*n+j,1,0); add((i-1)*n+j,n*n+i,1,0); add((i-1)*n+j,n*n+j,1,0); } else if(a[i][j]==1) add(S,n*n+j,1,0); else add(S,n*n+i,1,0); } } for(re int i=1;i<=n;++i) { for(re int j=0;j<n;++j) add(n*n+i,T,1,j); } dinic(); for(re int i=1;i<=n;++i) { for(re int j=i+1;j<=n;++j) { if(a[i][j]<2) continue; for(re int k=head[(i-1)*n+j];k;k=e[k].next) { if(e[k].v&&e[k].val==0) { a[i][j]=(e[k].v-n*n==j); a[j][i]=a[i][j]^1; } } } } for(re int i=1;i<=n;++i,puts("")) { for(re int j=1;j<=n;++j) printf("%d ",a[i][j]); } return 0; } ```