传送门
首先最大流等于最小割，那么可以转化为最小割树来做（不知道什么是最小割树的可以看看这题->这里）
具体的做法似乎是$hash[i][j]$表示最小割为$i$时点$j$是否与$S$连通
然后据Claris大爷说这题卡dinic，只能用EK
顺便吐槽一句，Claris大爷的代码真的不能看……
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x3f3f3f3f3 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 char buf[1<<21],*p1=buf,*p2=buf; 11 inline int read(){ 12 #define num ch-'0' 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch=='-')&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=3005; 22 int ver[N<<2],Next[N<<2],edge[N<<2],head[N],tot=1; 23 inline void add(int u,int v,int e){ 24 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 25 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=e; 26 } 27 int dep[N],q[N],n,m,S,T,ans; 28 bool bfs(){ 29 int l=0,r=1;memset(dep+1,-1,sizeof(int)*n);dep[q[0]=S]=0; 30 while(l<r){ 31 int u=q[l++]; 32 for(int i=head[u];i;i=Next[i]) 33 if(dep[ver[i]]<0&&edge[i]) 34 dep[ver[i]]=i,q[r++]=ver[i]; 35 } 36 return ~dep[T]; 37 } 38 int id[N],tmp[N]; 39 unsigned Pow=1,Hash[4][N]; 40 void solve(int L,int R){ 41 if(L==R) return; 42 for(int i=2;i<=tot;i+=2) 43 edge[i]=edge[i^1]=1; 44 S=id[L],T=id[R];int flow=0,j; 45 while(bfs()){ 46 ++flow; 47 for(int i=T;i!=S;i=ver[j^1]) --edge[j=dep[i]],++edge[j^1]; 48 } 49 Pow*=233; 50 for(int i=1;i<=n;++i) 51 if(~dep[i]) Hash[flow][i]+=Pow; 52 int l=L,r=R; 53 for(int i=L;i<=R;++i) 54 if(~dep[id[i]]) tmp[l++]=id[i]; 55 else tmp[r--]=id[i]; 56 memcpy(id+L,tmp+L,sizeof(int)*(R-L+1)); 57 solve(L,l-1),solve(r+1,R); 58 } 59 int main(){ 60 //freopen("testdata.in","r",stdin); 61 n=read(),m=read(); 62 for(int i=1,u,v;i<=m;++i) 63 u=read(),v=read(),add(u,v,1); 64 for(int i=1;i<=n;++i) id[i]=i; 65 solve(1,n); 66 for(int i=1;i<=n;++i) 67 for(int j=i+1;j<=n;++j) 68 for(int k=0;k<=3;++k) 69 if(Hash[k][i]!=Hash[k][j]) {ans+=k;break;} 70 printf("%d\n",ans); 71 return 0; 72 }
