VEXOBEN
Vexoben
Jun 28, 2018
It takes 7 minutes to read this article.

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2597

题意

给定 n 个点的完全图,一部分边是有向边,其余是无向边。试给无向边定向,最大化三元环(x,y,z)的个数。(即x到y有边,y到z有边,z到x有边)

n<=100

题解

不易直接求解,考虑补集转化。

显然三元环最多不会超过 C(n,3) 个。同时,如果存在(x,y,z)使(x->z,y->z),三元环数减一。换句话说,两条指向同一个点的边会使三元环数减一。

考虑费用流建模。我们用 Ei 表示第 i 条边在流网络上对应的点。流网络上的一条边(Ei->x,x是Ei的端点之一)表示 Ei 对应的比赛中,输的一方是 x。

然后就有:

1、 S->Ei, cap=1, cost=0

2、 Ei=(u,v) ①Ei->u cap=1,cost=0 (if a[u][v]!=1) ②Ei->v cap=1,cost=0 (if a[u][v]!=0)

3、 x->T, 且当流量为 c 时,费用为C(c,2)

第三种边需要用到拆边: x 向 T 连 n 条边,第 i 条边 cap=1, cost=i-1。显然每次会挑费用最小的走,可以得到流量为 c 时费用为C(c,2)

答案就是 C(n,3)-最小费用最大流

输出方案只要看 Ei 连出的 cap=0 的边指向谁就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+200;
const int M=2e5+10;
const int inf=0x3f3f3f3f;

int n,m,V,E=1,S,T,cost,a[105][105];
int u[N],v[N],fir[N],vis[N],dis[N],nex[M],arr[M],cap[M],len[M];
queue<int> Q;

inline void Add_Edge(int x,int y,int c,int l) {
	nex[++E]=fir[x];
	fir[x]=E; arr[E]=y; cap[E]=c; len[E]=l;
	nex[++E]=fir[y];
	fir[y]=E; arr[E]=x; cap[E]=0; len[E]=-l;
}

inline int Spfa() {
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[T]=0; Q.push(T);
	while (!Q.empty()) {
		int x=Q.front(); Q.pop(); vis[x]=0;
		for (int i=fir[x];i;i=nex[i]) {
			if (!cap[i^1]||dis[arr[i]]<=dis[x]+len[i^1]) continue;
			dis[arr[i]]=dis[x]+len[i^1];
			if (!vis[arr[i]]) vis[arr[i]]=1,Q.push(arr[i]);
		}
	}
	return dis[S]<inf;
}

inline int dfs(int x,int maxflow) {
	vis[x]=1;
	if (x==T||!maxflow) return maxflow;
	int ans=0;
	for (int i=fir[x];i;i=nex[i]) {
		if (dis[x]!=dis[arr[i]]+len[i]||vis[arr[i]]||!cap[i]) continue;
		int del=dfs(arr[i],min(maxflow,cap[i]));
		maxflow-=del; ans+=del;
		cap[i]-=del; cap[i^1]+=del;
		cost+=del*len[i];
	}
	return ans;
}

int main() {
	scanf("%d",&n);
	S=n+1; T=n+2; V=n+2;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			scanf("%d",&a[i][j]);
			if (i>=j) continue;
			++V; u[V]=i; v[V]=j;
			Add_Edge(S,V,1,0);
			if (a[i][j]!=1) Add_Edge(V,u[V],1,0);
			if (a[i][j]!=0) Add_Edge(V,v[V],1,0);
		}
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<n;j++) {
			Add_Edge(i,T,1,j-1);
		}
	}
	while (Spfa()) {
		vis[T]=1;
		while (vis[T]) {
			memset(vis,0,sizeof(vis));
			dfs(S,inf);
		}
	}
	for (int i=n+3;i<=V;i++) {
		int x=u[i],y=v[i];
		for (int j=fir[i];j;j=nex[j]) {
			if ((!(j&1))&&cap[j]==0) {
				if (arr[j]==x) a[x][y]=0,a[y][x]=1;
				else a[y][x]=0,a[x][y]=1;
				break;
			}
		}
	}
	int sum=n*(n-1)*(n-2)/6;
	printf("%d\n",sum-cost);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<n;j++) printf("%d ",a[i][j]);
		printf("%d\n",a[i][n]);
	}
	return 0;
}