1264E - Beautiful League - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010,inf=0x3f3f3f3f;
namespace WFFL{
int Fir[maxn],Nxt[maxn],Too[maxn],f[maxn],tot=1,w[maxn],dis[maxn];
int S=maxn-1,T=maxn-2,cur[maxn];
queue<int> q;bool vis[maxn];
void add(int a,int b,int c,int d){
Too[++tot]=b;f[tot]=c;w[tot]= d;Nxt[tot]=Fir[a];Fir[a]=tot;
Too[++tot]=a;f[tot]=0;w[tot]=-d;Nxt[tot]=Fir[b];Fir[b]=tot;
}
bool spfa(){
memset(dis,0x3f,sizeof(dis));
q.push(S);dis[S]=0;cur[S]=Fir[S];
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=Fir[u];i;i=Nxt[i]){
int v=Too[i];
if(f[i]&&dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
cur[v]=Fir[v];
if(!vis[v]){q.push(v);vis[v]=1;}
}
}
}
return dis[T]!=inf;
}
int find(int u,int limit){
if(u==T)return limit;
vis[u]=1;
int flow=0;
for(int &i=cur[u];i;i=Nxt[i]){
int v=Too[i];
if(f[i]&&!vis[v]&&dis[v]==dis[u]+w[i]){
int t=find(v,min(f[i],limit-flow));
if(t)f[i]-=t,f[i^1]+=t,flow+=t;
else dis[v]=-inf;
}
if(flow==limit)break;
}
vis[u]=0;
return flow;
}
int dinic(){
int cost=0;
while(spfa())cost+=dis[T]*find(S,inf);
return cost;
}
}
int n,m,G[52][52],cd[52],id[52][52];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int a,b;
scanf("%d%d",&a,&b);
G[a][b]=1;
}
int cnt=n;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j){
++cnt;
WFFL::add(WFFL::S,cnt,1,0);
if(!G[j][i]){
WFFL::add(cnt,i,1,0);
id[i][j]=WFFL::tot;
}
if(!G[i][j]){
WFFL::add(cnt,j,1,0);
id[j][i]=WFFL::tot;
}
}
for(int i=1;i<=n;++i)
for(int j=cd[i];j<n;++j)
WFFL::add(i,WFFL::T,1,j);
WFFL::dinic();
for(int i=1;i<=n;++i,puts(""))
for(int j=1;j<=n;++j)
printf("%d",WFFL::f[id[i][j]]);
return 0;
}