Luogu

分析

首先三元环个数不是很好算，考虑用总数减去不是三元环的。

总数显然是
$$
{n\choose 3}=\frac{n(n-1)(n-2)}{6}
$$
考虑三个点要怎样才不会构成三元环，可以发现有一个点的入度为 $2$ 即可。

进一步发现，如果 $u$ 的入度为 $d$ ，那么整张图会产生 $d\choose 2$ 个不是三元环的三元组。

考虑差分。对于一个点 $u$ ，如果它的入度增加了 $1$ 变成了 $deg$ ，那么整张图会减少 $deg-1$ 个三元环。

考虑把减少的三元环当做费用，构建费用流模型：

• 源点向每条未定向的边连容量为 $1$ 、费用为 $0$ 的边。
• 每条未定向的边向两个端点各连一条容量为 $1$ 、费用为 $0$ 的边，表示只能使一个端点的入度增加 $1$ 。
• 每个端点向汇点连若干条容量为 $1$ 的边，费用分别为 $deg,deg+1,\cdots,n-1$ ，表示度数增加 $1$ 要减少这么多个三元环。

那么跑最小费用最大流即可得到多减少的三元环个数，然后就很好算答案了。

至于输出方案的话，看一下对应的边是否满流即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,m,s,t,tot=0;
int a[110][110],id[110][110],deg[110];
int edge_id[110][110],node_id[110];

struct edge { int v,w,c,nxt; } e[1000000];
int head[100000],e_cnt=2;
inline void addEdge(int u,int v,int w,int c) {
    e[e_cnt]=(edge){v,w,c,head[u]},head[u]=e_cnt++;
    e[e_cnt]=(edge){u,0,-c,head[v]},head[v]=e_cnt++;
}

int dis[100000],inq[100000],lst[100000];
inline int spfa() {
    memset(dis,0x3f,(t+1)<<2),memset(lst,0,(t+1)<<2);
    queue<int> Q; Q.push(s),dis[s]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w,c=e[i].c;
            if (w&&dis[u]+c<dis[v]) {
                dis[v]=dis[u]+c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[t]!=0;
}

inline int mcmf() {
    int res=0;
    while (spfa()) {
        int f=2e9;
        for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        res+=dis[t]*f;
    }
    return res;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            a[i][j]=read();
            if (a[i][j]==1) ++deg[j];
        }
    for (re int i=1;i<=n;++i)
        for (re int j=i+1;j<=n;++j)
            edge_id[i][j]=++tot;
    for (re int i=1;i<=n;++i) node_id[i]=++tot;
    s=0,t=tot+1;
    for (re int i=1;i<=n;++i)
        for (re int j=i+1;j<=n;++j) {
            if (a[i][j]!=2) continue;
            addEdge(s,edge_id[i][j],1,0);
            id[j][i]=e_cnt,addEdge(edge_id[i][j],node_id[i],1,0);
            id[i][j]=e_cnt,addEdge(edge_id[i][j],node_id[j],1,0);
        }
    int ans=0;
    for (re int i=1;i<=n;++i) {
        ans+=deg[i]*(deg[i]-1)/2;
        for (re int j=deg[i]+1;j<n;++j)
            addEdge(node_id[i],t,1,j-1);
    }
    ans+=mcmf();
    printf("%d\n",n*(n-1)*(n-2)/6-ans);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            if (a[i][j]!=2) printf("%d",a[i][j]);
            else printf("%d",1-e[id[i][j]].w);
            putchar(" \n"[j==n]);
        }
    return 0;
}