竞赛图中有一些边已经定向，现在要你给剩下的边定向，使得三元环的数量尽可能多。
\(n\le100\)
正难则反。
考虑三个点不形成三元环（剪刀石头布）的情况：必然有一个点入度为\(2\)，一个点出度为\(2\)，一个点入度出度都为\(1\)。
我们考虑枚举入度为\(2\)的那个点，这样不形成三元环的数量就为\(\sum\binom{in_i}{2}\)，答案就为\(\binom{n}{3}-\sum\binom{in_i}{2}=\frac{n(n-1)(n-2)}{6}-\sum\frac{in_i^2-in_i}{2}=\frac{n(n-1)(n-2)}{6}+\frac{n(n-1)}{2}-\sum\frac{in_i^2}{2}\)。
发现前面的都是定值，所以要最大化三元环数量就只要最小化\(\sum\frac{in_i^2}{2}\)就行了。
而这个东西显然是一个下凸函数，所以拆一下边就好了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e5+5;
struct edge{int to,nxt,w,cost;}a[N<<4];
int n,S,T,tot,g[105][105],du[N],tmp[N],X[N],Y[N];
int head[N],cnt=1,dis[N],vis[N],pe[N],ans;
queue<int>Q;
void link(int u,int v,int w,int cost){
a[++cnt]=(edge){v,head[u],w,cost};head[u]=cnt;
a[++cnt]=(edge){u,head[v],0,-cost};head[v]=cnt;
}
bool spfa(){
memset(dis,63,sizeof(dis));
dis[S]=0;Q.push(S);
while (!Q.empty()){
int u=Q.front();Q.pop();
for (int e=head[u];e;e=a[e].nxt){
int v=a[e].to;
if (a[e].w&&dis[v]>dis[u]+a[e].cost){
dis[v]=dis[u]+a[e].cost;pe[v]=e;
if (!vis[v]) vis[v]=1,Q.push(v);
}
}
vis[u]=0;
}
if (dis[T]==dis[0]) return false;
ans+=dis[T];
for (int i=T;i!=S;i=a[pe[i]^1].to)
--a[pe[i]].w,++a[pe[i]^1].w;
return true;
}
int main(){
n=gi();S=n+1;T=tot=n+2;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j){
g[i][j]=gi();
if (g[i][j]==2){
if (i>j) continue;
++tot;X[tot]=i;Y[tot]=j;
link(S,tot,1,0);
link(tot,i,1,0);link(tot,j,1,0);
++tmp[i];++tmp[j];
}
else du[i]+=g[i][j];
}
for (int i=1;i<=n;++i){
ans+=du[i]*du[i];
for (int j=1;j<=tmp[i];++j)
link(i,T,1,2*(du[i]+j)-1);
}
while (spfa()) ;
printf("%d\n",n*(n-1)*(n-2)/6-(ans-n*(n-1)/2)/2);
for (int i=n+3;i<=tot;++i){
int chos;
for (int e=head[i];e;e=a[e].nxt)
if (a[e].to!=S&&!a[e].w) {chos=a[e].to;break;}
if (chos==X[i]) g[X[i]][Y[i]]=1,g[Y[i]][X[i]]=0;
else g[X[i]][Y[i]]=0,g[Y[i]][X[i]]=1;
}
for (int i=1;i<=n;++i,puts(""))
for (int j=1;j<=n;++j)
printf("%d ",g[i][j]);
return 0;
}原文：https://www.cnblogs.com/zhoushuyu/p/9146420.html