不得不说这思路真是太妙了
考虑能构成三元组很难，那我们考虑不能构成三元组的情况是怎么样
就是说一个三元组$(a,b,c)$，其中$a$赢两场，$b$赢一场，$c$没有赢
所以如果第$i$个人赢了$w_i$场，那么总共的不能构成的三元组就是$sum_i{w_i*(w_i-1)}{2}$
最大化满足的数量，就是最小化不满足的数量，就是最小化上面那个式子
那么我们考虑构建网络流
建源汇
对第$i$个人，从它向汇点连容量为$n$的边
对于每一对$i,j$之间的比赛建一个点$C_{i,j}$，如果这场比赛尚未进行，那么源点向$C_{i,j}$连容$1$费$0$的边，$C_{i,j}向$i$和$j$连容$1$费$0$的边,表示这场比赛只能改变一个点的赢的场数
我们要最小化上式，那么我们考虑在费用上做文章
每个点$i$向汇点连边，但因为费用的增加是一次比一次大的，所以我们考虑把这条边拆成$n$条边，容量为$1$费用分别为$0,1,2...$
因为费用流每一次都先增广最小的费用，所以只要求出最小费用最大流即可
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 const int N=50005,M=100005; 21 int head[N],Next[M],ver[M],edge[M],cost[M],tot=1; 22 inline void add(int u,int v,int e,int c=0){ 23 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e,cost[tot]=c; 24 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=0,cost[tot]=-c; 25 } 26 int dis[N],vis[N],cur[N],S,T,ans; 27 queue<int> q; 28 bool spfa(){ 29 memset(dis,-1,sizeof(dis)); 30 memset(vis,0,sizeof(vis)); 31 memcpy(cur,head,sizeof(head)); 32 q.push(T),dis[T]=0,vis[T]=1; 33 while(!q.empty()){ 34 int u=q.front();q.pop(),vis[u]=0; 35 for(int i=head[u];i;i=Next[i]) 36 if(edge[i^1]){ 37 int v=ver[i],c=cost[i]; 38 if(dis[v]<0||dis[v]>dis[u]-c){ 39 dis[v]=dis[u]-c; 40 if(!vis[v]) vis[v]=1,q.push(v); 41 } 42 } 43 } 44 return ~dis[S]; 45 } 46 int dfs(int u,int limit){ 47 if(!limit||u==T) return limit; 48 int flow=0,f;vis[u]=1; 49 for(int i=cur[u];i;cur[u]=i=Next[i]){ 50 int v=ver[i]; 51 if(dis[v]==dis[u]-cost[i]&&!vis[v]&&(f=dfs(v,min(limit,edge[i])))){ 52 flow+=f,limit-=f; 53 edge[i]-=f,edge[i^1]+=f; 54 ans-=f*cost[i]; 55 if(!limit) break; 56 } 57 } 58 vis[u]=0; 59 return flow; 60 } 61 void zkw(){while(spfa()) dfs(S,inf);} 62 int mp[105][105],win[105][105],n,cnt; 63 int main(){ 64 //freopen("testdata.in","r",stdin); 65 n=read(); 66 for(int i=1;i<=n;++i) 67 for(int j=1;j<=n;++j) 68 mp[i][j]=read(); 69 S=0,cnt=n; 70 for(int i=1;i<=n;++i) 71 for(int j=1;j<i;++j){ 72 add(S,++cnt,1); 73 if(mp[i][j]==0||mp[i][j]==2) add(cnt,i,1),win[j][i]=tot-1; 74 if(mp[i][j]==1||mp[i][j]==2) add(cnt,j,1),win[i][j]=tot-1; 75 } 76 T=cnt+1; 77 for(int i=1;i<=n;++i) 78 for(int j=0;j<n;++j) 79 add(i,T,1,j); 80 ans=n*(n-1)*(n-2)/6; 81 zkw(); 82 printf("%d ",ans); 83 for(int i=1;i<=n;++i){ 84 for(int j=1;j<=n;++j) 85 printf("%s%d",j==1?"":" ",!win[i][j]||edge[win[i][j]]?0:1); 86 putchar(10); 87 } 88 return 0; 89 }