Description：

给一个竞赛图，有一些边还没确定方向，为他们确定方向使得有向三元环最多。

$1\leqslant n\leqslant 100$

Solution：

差一点就想到了。

首先可以想到某道 $\text{POI}$ 题让找一个欧拉回路，这个有些类似，但也不太一样，首先总的三元环个数一定是 $C^n_3$ ，那么我们可以减掉不是有向三元环的个数，具体来说分析一下三元环的性质会发现如果有两条边都指向了一个点那么整张图就会失掉一个三元环，然后有一个非常重要但是我没想到的转化是如果当前入度为 $deg$ ，那么再加一个入度会使整张图失去 $deg$ 个三元环，想到这个就很好说了，把边看成左部点，点看成右部点，那么从边向两个点连边，从源点向边连容量为 $1$ 的边，那么一个流就代表为某个点增加一个入度，因此从每个点向汇点分别连容量为 $1$ ，费用为 $0,1,2,3,\dots$ 的边即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 110

int a[MAXN][MAXN];

int to(int i,int j){return (i - 1) * n + j;}

int s,t;

struct edge

{

	int to,nxt,f,w;

}e[(MAXN * MAXN + MAXN * MAXN + MAXN * MAXN * 2) * 2];

int edgenum = 0;

int lin[MAXN * MAXN + MAXN];

void add(int a,int b,int f,int w)

{

	e[edgenum] = (edge){b,lin[a],f, w};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-w};lin[b] = edgenum++;

	return;

}

int d[MAXN * MAXN + MAXN],pre[MAXN * MAXN + MAXN],rate[MAXN * MAXN + MAXN];

bool v[MAXN * MAXN + MAXN];

#define INF 0x3f3f3f3f

bool SPFA()

{

	memset(d,0x3f,sizeof(d));d[s] = 0;

	queue<int> q;q.push(s);

	rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].w && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].w;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return (d[t] != INF);

}

int flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t] * d[t];

}

int EK()

{

	int ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int calc(int x,int y)

{

	if(x == y)return 0;

	int xx = x,yy = y;

	if(x > y)swap(x,y);

	for(int i = lin[to(x,y)];i != -1;i = e[i].nxt)

	{

		if(e[i].to == s)continue;

		if(e[i].f == 0)

		{

			if(e[i].to == n * n + xx)

			{

				return 0;

			}

			else

			{

				return 1;

			}

		}

	}

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	s = n * n + n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			add(i + n * n,t,1,j - 1);

			scanf("%d",&a[i][j]);

			if(i >= j)continue;

			add(s,to(i,j),1,0);

			if(a[i][j] == 0 || a[i][j] == 2)add(to(i,j),i + n * n,1,0);

			if(a[i][j] == 1 || a[i][j] == 2)add(to(i,j),j + n * n,1,0);

		}

	}

	cout << n * (n - 1) * (n - 2) / 6 - EK() << endl;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			printf("%d ",calc(i,j));

		}

		puts("");

	}

	return 0;

}