\(~\)
BZOJ 2597
LUOGU 4249
Description
在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到A胜过B，B胜过C而C又胜过A的有趣情况，不妨形象的称之为剪刀石头布情况。有的时候，无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生，即有多少对无序三元组(A, B, C)，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要，将(A, B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B, A)视为相同的情况。
有N个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。
Input
输入文件的第1行是一个整数N，表示参加比赛的人数。
之后是一个N行N列的数字矩阵：一共N行，每行N列，数字间用空格隔开。
在第(i+1)行的第j列的数字如果是1，则表示i在已经发生的比赛中赢了j；该数字若是0，则表示在已经发生的比赛中i败于j；该数字是2，表示i和j之间的比赛尚未发生。数字矩阵对角线上的数字，即第(i+1)行第i列的数字都是0，它们仅仅是占位符号，没有任何意义。
输入文件保证合法，不会发生矛盾，当i≠j时，第(i+1)行第j列和第(j+1)行第i列的两个数字要么都是2，要么一个是0一个是1。
Output
输出文件的第1行是一个整数，表示在你安排的比赛结果中，出现了多少剪刀石头布情况。
输出文件的第2行开始有一个和输入文件中格式相同的N行N列的数字矩阵。第(i+1)行第j个数字描述了i和j之间的比赛结果，1表示i赢了j，0表示i负于j，与输入矩阵不同的是，在这个矩阵中没有表示比赛尚未进行的数字2；对角线上的数字都是0。输出矩阵要保证合法，不能发生矛盾。
Sample Input
3
0 1 2
0 0 2
2 2 0
Sample Output
1
0 1 0
0 0 1
1 0 0
HINT
100%的数据中，N≤ 100。
简化题意：
给定一张图，每两点之间有一条有向边或无向边，把所有无向边定向，使图中三元环个数尽量多。
从整个图的 \(n\) 个点中任取 \(3\) 个点，方案数为 \(C^{3}_{n}=\frac{n!}{3!(n-3)!}=\frac{n(n-1)(n-2)}{6}\)，
那么如果一个三元组不是三元环，那么有一个点的出度为 \(2\)，
我们假设一个点的出度为 \(d\)，那么对于这个点，三元环会减少 \(\frac{d (d-1)}{2}\)，
?
所以三元环的数量为： \(C^{3}_{n}- \sum_{i=1}^nC_{d[i]}^{2}=C^{3}_{n}- \sum_{i=1}^n\frac{d[i] (d[i]-1)}{2}\)，
所以我们要最小化：\(\sum_{i=1}^n\frac{d[i] (d[i]-1)}{2}\)，
怎么做呢？
如果我们对于一条无向边，可能让 \(x\) 出度 \(+1\)，也可能让 \(y\) 出度 \(+1\)，非黑即白，所以我们可以考虑费用流。
观察式子 \(\frac{d[i](d[i]-1)}{2}\)，容(hen)易(nan)想到小学等差数列求和公式，于是我们可以将一个点的贡献看成 \((0+1+2+3+……+d[i]-1)\)，所以建图就可以这样搞了：
#include<bits/stdc++.h>
using namespace std;
const int maxn=110,maxm=maxn*maxn,inf=0x3f3f3f3f;
char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
x=0;
T f=1, ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-1, ch=getchar();
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
x*=f;
}
char Out[1<<24],*fe=Out;
inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
template<typename T>inline void write(T x,char c)
{
if (!x) *fe++=48;
if (x<0) *fe++='-', x=-x;
T num=0, ch[20];
while (x) ch[++num]=x%10+48, x/=10;
while (num) *fe++=ch[num--];
*fe++=c;
}
int ver[maxm<<3],edge[maxm<<3],Next[maxm<<3],cost[maxm<<3],head[maxm],len=1;
inline void add(int x,int y,int z,int c)
{
ver[++len]=y,edge[len]=z,cost[len]=c,Next[len]=head[x],head[x]=len;
ver[++len]=x,edge[len]=0,cost[len]=-c,Next[len]=head[y],head[y]=len;
}
int s,t;
int dist[maxm];
bool vis[maxm];
inline bool spfa()
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
queue<int>q;q.push(s);
dist[s]=0,vis[s]=1;
while (!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for (int i=head[x]; i; i=Next[i])
{
if (!edge[i]) continue;
int y=ver[i];
if (dist[y]>dist[x]+cost[i])
{
dist[y]=dist[x]+cost[i];
if (!vis[y]) q.push(y),vis[y]=1;
}
}
}
if (dist[t]==inf) return false;
else return true;
}
int ans;
inline int get(int x,int low)
{
vis[x]=1;
if (x==t) return low;
int tmp=low;
for (int i=head[x]; i; i=Next[i])
{
int y=ver[i];
if (edge[i] && dist[y]==dist[x]+cost[i] && (!vis[y] || y==t))
{
int a=get(y,min(tmp,edge[i]));
if (a>0)
{
ans+=a*cost[i];
edge[i]-=a;
edge[i^1]+=a;
if (!(tmp-=a)) break;
}
}
}
return low-tmp;
}
inline void NetFlow()
{
while (spfa())
{
vis[t]=1;
while (vis[t])
{
memset(vis,0,sizeof(vis));
get(s,inf);
}
}
}
int n,a[maxn][maxn];
inline int hs(int i,int j)
{
return (i-1)*n+j;
}
int main()
{
read(n); s=0,t=n*n+n+1;
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
{
read(a[i][j]);
if (i>=j) continue;
if (a[i][j]==2) add(s,hs(i,j),1,0),add(hs(i,j),i+n*n,1,0),add(hs(i,j),j+n*n,1,0);
else if (a[i][j]==1) add(s,j+n*n,1,0);
else add(s,i+n*n,1,0);
}
for (int i=1; i<=n; ++i)
for (int j=0; j<n; ++j) add(i+n*n,t,1,j);
NetFlow();
int sum=((n-1)*(n-2)*n)/6;
write(sum-ans,'\n');
for (int i=1; i<=n; ++i)
for (int j=i+1; j<=n; ++j)
{
if (a[i][j]<2) continue;
for (int k=head[hs(i,j)]; k; k=Next[k])
if (ver[k] && !edge[k]) a[i][j]=(ver[k]-n*n==j),a[j][i]=a[i][j]^1;
}
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j) write(a[i][j],j<n?' ':'\n');
flush();
return 0;
}BZOJ 2597: [Wc2007]剪刀石头布 最小费用最大流
原文：https://www.cnblogs.com/G-hsm/p/11318263.html