CF1264E - Beautiful League

题目大意

给定一张竞赛图，其中一些边已经确定

现在求确定剩余边的方向，使得最终图上三元环个数最大


分析

三元问题着实难以处理

考虑什么样的三个点$(x,y,z)$无法构成一个环：

三个点恰好存在一个点$x$得到两条入边，即$x\leftarrow y,x\leftarrow z$

此时无法构成环


于是问题转化为统计$x$的入度$ind_x$，减少的三元环个数就是$\sum \binom{ind_i} {2}$

考虑用网络流计算答案，每一条边$(u,v)$可以选择从$S$流向$u$或者$v$

一个点得到$i$的流量付出$\binom{i} {2}$的代价流出$T$

因此每个点向$T$连$n-1$条流量为$1$，代价分别为为$\binom{j} {2}-\binom{j-1} {2}$的边

求满流最小费用即可，输出方案容易根据流量情况判断

复杂度为$O(\text{MCMF}(n^2,n^2))$ 或者$O(\text{MCMF}(n,n^2))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int N=2e5+10,INF=1e9+10;

int n,m,S,T,V;
struct Edge{
	int to,nxt,w,c;
} e[N];
int head[N],ecnt=1;
void AddEdge(int u,int v,int w,int c){
	e[++ecnt]=(Edge){v,head[u],w,c};
	head[u]=ecnt;
}
void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }

int ans,dis[N];
char s[N];
int inq[N],pre[N],w[N];
int mk[110][110];

int main(){
	n=rd(),m=rd(),S=n+1,T=V=S+1;
	rep(i,1,n) rep(j,1,n-1) Link(i,T,1,j*(j-1)/2-(j-1)*(j-2)/2);
	memset(mk,-1,sizeof mk);
	while(m--) {
		int u=rd(),v=rd();
		if(u<v) mk[u][v]=1;
		else mk[v][u]=0;
	}
	rep(i,1,n) rep(j,i+1,n) {
		Link(S,++V,1,0);
		if(mk[i][j]!=0) Link(V,j,1,0);
		if(mk[i][j]!=1) Link(V,i,1,0);
	}
	while(1) {
		static queue <int> que;
		rep(i,1,V) dis[i]=INF;
		dis[S]=0,que.push(S),w[S]=INF;
		while(!que.empty()) {
			int u=que.front(); que.pop();
			inq[u]=0;
			for(int i=head[u];i;i=e[i].nxt) {
				int v=e[i].to,c=e[i].c;
				if(!e[i].w || dis[v]<=dis[u]+c) continue;
				dis[v]=dis[u]+c,w[v]=min(e[i].w,w[u]),pre[v]=i;
				if(!inq[v]) que.push(v),inq[v]=1;
			}
		}
		if(dis[T]==INF) break;
		int c=w[T]; ans+=dis[T]*c;
		for(int u=T;u!=S;u=e[pre[u]^1].to) e[pre[u]].w-=c,e[pre[u]^1].w+=c;
	}
	memset(mk,0,sizeof mk);
	rep(a,1,n) rep(b,a+1,n) {
		int u=++T;
		for(int i=head[u];i;i=e[i].nxt) if(e[i].to<=n && !e[i].w) {
			if(e[i].to==b) mk[a][b]=1;
			else mk[b][a]=1;
		}
	}
	rep(i,1,n) {
		rep(j,1,n) putchar(mk[i][j]+'0');
		puts("");
	}
}