RT

这两个都是我写的，一个是半个月前，一个是现在的

#include<bits/stdc++.h>
using namespace std;
const int maxn=5655;
int n,m,i,j,t,k,s,a[105][105],head[maxn],N,id[105][105],S,T,cur[maxn];//,si;
struct Edge
{
    int nxt,aim,len,fei;
}edge[maxn*4+155*155*2];
inline void add_edge(int x,int y,int le,int fe)
{
    edge[++N]=(Edge){head[x],y,le,fe};head[x]=N;
    edge[++N]=(Edge){head[y],x,0,-fe};head[y]=N;
}
int dis[maxn],lev[maxn];bool ins[maxn];
queue<int> Q;
bool SPFA()
{
    Q.push(S);//int sq=1;
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[S]=0;lev[S]=0;
    while (!Q.empty())
    {
        int x=Q.front();Q.pop();ins[x]=0;//--sq;
        for (int i=head[x];~i;i=edge[i].nxt)
         if (edge[i].len>0)
        {
            int des=edge[i].aim;
            if (dis[des]>edge[i].fei+dis[x])
            {
                dis[des]=edge[i].fei+dis[x];
                if (!ins[des])
                {
                    ins[des]=1;Q.push(des);
                    //++sq;si=max(si,sq);
                    //if (si>1000) printf("wryy! %d\n",si);A
                }
            }
        }
    }
    return dis[T]<=1000000;
}
int dfs(int x,int y)
{
    //printf("%d %d\n",x,y);
    if (x==T) return y;
    int used=0;ins[x]=1;
    for (int i=cur[x];~i;i=edge[i].nxt)
    {
        int des=edge[i].aim;cur[x]=i;
        if (dis[des]!=edge[i].fei+dis[x]|| !edge[i].len|| ins[des]) continue;
        int now=dfs(des,min(y-used,edge[i].len));
        edge[i].len-=now;edge[i^1].len+=now;used+=now;
        if (used==y) 
        {
            ins[x]=0;
            return used;
        }
    }
    ins[x]=0;
    return used;
}
void dinic()
{
    //int dd=0;
    while (SPFA())
    {
        //printf("sioj\n");
        for (int i=1;i<=T;++i) cur[i]=head[i];
        //dd+=
        dfs(S,1e9);
        //printf("flow:%d\n",dd);
    }
}
int main()
{
    //freopen("B.in","r",stdin);
    //freopen("B.out","w",stdout);
    N=-1;memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for (i=1;i<=n;++i)
     for (j=1;j<=n;++j)
      scanf("%d",&a[i][j]);
    t=n;S=n+(n-1)*n/2+1;T=S+1;
    for (i=1;i<=n;++i)
     for (j=i+1;j<=n;++j)
    {
        ++t;
        add_edge(S,t,1,0);
        id[i][j]=N+1;id[j][i]=N+2;
        if (a[i][j]==2) add_edge(t,i,1,0),add_edge(t,j,1,0);
        else if (a[i][j]==0) add_edge(t,j,1,0);
        else add_edge(t,i,1,0);
    }//printf("%d %d %d\n",t,S,T);
     
    for (i=1;i<=n;++i)
     for (j=1;j<=n;++j) add_edge(i,T,1,j*2-1);
    //printf("043029384\n");
    dinic();//printf("size of queue %d\n",si);
    for (i=1;i<=n;++i)
    {
        for (j=1;j<=n;++j)
        {
            int now=a[i][j];
            if (now==2) now=(edge[id[i][j]].len^1);
            a[i][j]=now;
            //printf("%d%c",now,(j==n?'\n':' '));
        }
    }s=0;
    for (i=1;i<=n;++i)
     for (j=1;j<=n;++j) if (i!=j)
      for (k=1;k<=n;++k) if (j!=k&&i!=k)
       s+=(a[i][j]&&a[j][k]&&a[k][i]);
    //printf("%d\n",s);
    s/=3;
    printf("%d\n",s);
    for (i=1;i<=n;++i)
    {
        for (j=1;j<=n;++j)
        {
            //int now=a[i][j];
            //if (now==2) now=(edge[id[i][j]].len^1);
            //a[i][j]=now;
            printf("%d%c",a[i][j],(j==n?'\n':' '));
        }
    }
    return 0;
}

这是AC的

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,t,k,s,N,S,T,head[5325],b[105][105],a[105][105];
int dis[5325],cur[5325];bool inq[5325];
struct Edge
{
	int nxt,aim,flo,len;
}edge[100405];

inline int add_edge(int x,int y,int ff,int le)
{
	edge[++N]=(Edge){head[x],y,ff,le};head[x]=N;
	edge[++N]=(Edge){head[y],x,0,-le};head[y]=N;
}

queue<int> Q;
bool SPFA()
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[S]=0;Q.push(S);
	while (!Q.empty())
	{
		int x=Q.front();Q.pop();
		inq[x]=0;cur[x]=head[x];
		for (int i=head[x];~i;i=edge[i].nxt)
		 if (edge[i].flo)
		{
			int des=edge[i].aim;
			if (dis[des]>dis[x]+edge[i].len)
			{
				dis[des]=dis[x]+edge[i].len;
				if (!inq[des]) Q.push(des),inq[des]=1;
			}
		}
	}
	return dis[T]<1e9;
}
int dfs(int x,int y)
{
	inq[x]=1;
	if (x==T) {inq[x]=0;return y;}
	int used=0;
	for (int i=cur[x];~i;i=edge[i].nxt)
	{
		int des=edge[i].aim;cur[x]=i;
		if (dis[des]!=dis[x]+edge[i].len||inq[des]||!edge[i].flo) continue;
		int ad=dfs(des,min(y-used,edge[i].flo));
		s+=ad*edge[i].len;edge[i].flo-=ad;edge[i^1].flo+=ad;used+=ad;
		//if (ad&&edge[i].len!=0) printf("flow %d %d\n",x,des);
		if (used==y){inq[x]=0;return y;}
	}
	//cur[x]=-1;
	inq[x]=0;
	return used;
}
void dinic()
{
	int ret=0;
	while (SPFA())
	{
		//printf("%d\n",ret);
		ret+=dfs(S,1e9);
	}
	//printf("flo:%d\n",ret);
	//return ret;
}

int main()
{
	memset(head,0xff,sizeof(head));N=-1;memset(cur,0xff,sizeof(cur));
	scanf("%d",&n);S=n+1;T=S+1;t=T;
	for (i=1;i<=n;++i)
	 for (j=1;j<=n;++j) scanf("%d",&a[i][j]);
	for (i=1;i<=n;++i)
	{
		for (j=1+i;j<=n;++j)
		{
			if (a[i][j]<2)
			{
				add_edge(S,(a[i][j]?i:j),1,0);
			}
			else
			{
				++t;
				add_edge(S,t,1,0);
				add_edge(t,i,1,0);
				b[i][j]=N;
				add_edge(t,j,1,0);
				b[j][i]=N;
			}
		}
	}
	for (i=1;i<=n;++i)
	{
		//add_edge(S,g(2,i),n-1,0);
		//add_edge(g(0,i),T,1,0),add_edge(g(1,i),T,1,0);
		for (j=0;j<=n-1;++j) add_edge(i,T,1,j);
	}
	s=0;
	dinic();//printf("%d\n",s);
	s=(n*(n-1)*(n-2)/6-s);
	printf("%d\n",s);
	for (i=1;i<=n;++i)
	{
		for (j=1;j<=n;++j)
		{
			if (a[i][j]<2) printf("%d ",a[i][j]);
			else printf("%d ",edge[b[i][j]].flo);
		}
		puts("");
	}
	return 0;
}

这是RE的