考虑构建网络流模型
把一个流量看成一只奶牛的攻击过程，那么答案就是最大流
因为每只奶牛只能操作一波，所以构造分层图，一层相当于一步
第一层就是初始状态，从 $S$ 向所有 $J$ 奶牛连一条流量为 $1$ 的边，表示只有一只 $J$
下一层，表示奶牛走一步后的状态，每只 $J$ 向下一层走一步可以到达的点连流量为 $1$ 的边，当然奶牛可以不走，所以也要向下一层原来的位置连流量为 $1$ 的边
再下一层就可以考虑奶牛攻击了，但是因为每个位置只能站一只奶牛，所以这一层还要再拆成两层，对于点之间连流量为 $1$ 的边，表示一个位置只能站一只奶牛，然后再把所有的 $T$牛 连一条流量为 $1$ 的边到 $T$（汇点），因为一只 $T$牛 只能被打翻一次
最后答案就是最大流
总结一下就是图分成四层，每一步慢慢考虑
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,M=4e6+7,INF=1e9+7; int fir[N],from[M],to[M],val[M],cntt=1; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; } int dep[N],Fir[N],S,T; queue <int> q; bool BFS() { for(int i=S;i<=T;i++) Fir[i]=fir[i],dep[i]=0; q.push(S); dep[S]=1; int x; while(!q.empty()) { x=q.front(); q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; dep[v]=dep[x]+1; q.push(v); } } return dep[T]>0; } int DFS(int x,int mxf) { if(x==T||!mxf) return mxf; int fl=0,res; for(int &i=Fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]!=dep[x]+1||!val[i]) continue; if( res=DFS(v,min(mxf,val[i])) ) { mxf-=res; fl+=res; val[i]-=res; val[i^1]+=res; if(!mxf) break; } } return fl; } inline int Dinic() { int res=0; while(BFS()) res+=DFS(S,INF); return res; } int n,m; char s[N]; int main() { n=read(),m=read(); scanf("%s",s+1); S=0,T=n*4+1; int a,b; for(int i=1;i<=n;i++) { if(s[i]=='J') add(S,i,1),add(i,n+i,1); if(s[i]=='T') add(n*3+i,T,1); else add(n+i,n*2+i,1); } for(int i=1;i<=m;i++) { a=read(),b=read(); if(s[a]!='T'&&s[b]!='T') add(a,n+b,1),add(b,n+a,1); if(s[a]!='T'&&s[b]=='T') add(n*2+a,n*3+b,1); if(s[b]!='T'&&s[a]=='T') add(n*2+b,n*3+a,1); } printf("%d",Dinic()); return 0; }