Vexoben
Jun 28, 2018
题目链接：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;
}