YbtOJ 574「二分图匹配」孤立点集
题目链接：YbtOJ #574
小 A 有一张 n 个点 m 条边的 DAG，他想要知道最多能选出多少个点，使得这些点中不存在某两个点满足 其中一个点能到达另一个点，并希望你给出任意一种点数最多的构造方案。
更进一步，他想要知道每个点是否 可能 出现在一种点数最多的构造方案中。
1le nle100，1le mle 10^3。
Solution
由 Dilworth 定理，一个 DAG 中最长反链的大小，等于其中最小可重链覆盖大小。
最小可重链覆盖：在 DAG 中选出若干条链，经过每个点至少一次，一个点可被一条链经过多次，且链数尽量少。
考虑将每个点拆成出点和入点，对于一条边 xrightarrow y，连接 x_o 与 y_i。
那么我们就可以在这个二分图 G=langle langle V_o,V_irangle,E’rangle 上跑最大匹配。
每匹配 1 条边，链的个数就减少 1，则有最小链覆盖的大小等于 n 减去最大匹配的大小。
继续考虑如何从二分图最大匹配中，构造出最长反链。
首先需要构造二分图最大独立集。
我们可以从右侧的非匹配点开始 DFS，右侧的点只能走非匹配边向左访问，左侧的点只能走匹配边向右访问：
取左侧被 DFS 到的点，以及右侧没被 DFS 到的点，我们可以证明这些点为一个最小点覆盖。
最小点覆盖：选取最少的点，覆盖每条边，也就是说每条边的两个端点至少有一个被选中了。
最大独立集等于最小点覆盖的补集，那么只要选出左侧没被 DFS 到的点和右侧被 DFS 到的点就行了。
回到 DAG 的情况（注意到我们举的例子并不是 DAG 导出的二分图，所以这个例子不能用来解释最长反链）：
令最大独立集为 I，考虑选出所有 x_o,x_i 都属于 I 的点，记做集合 A，它们构成一个最长反链。
然后是第三问，这只要默认该点被选中，也就是删除这个点和与其有偏序关系的所有点后，再求一次最长反链，如果最长反链的大小只减小了 1，那么这个点就能在最长反链中，否则不能。
时间复杂度：O(n^{3.5})。
Code
代码语言：javascript复制#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=105,M=1e3 10,P=N*2,E=(N*N N*2)*2,inf=2e9;
int n,m,fir[P],nxt[E],son[E],w[E],tot=1,S,T,cnt,cur[P],D[P],visL[N],visR[N],gT,Mk[N],Ans,r[N];
I void Add(CI x,CI y,CI z){nxt[ tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,nxt[ tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0;}
#define to son[i]
bitset<N> b[N];
queue<int> q;
I bool Bfs(){RI i,u;W(!q.empty()) q.pop();memset(D,-1,sizeof(D)),D[S]=0,q.push(S);W(!q.empty()) for(u=q.front(),q.pop(),i=fir[u];i;i=nxt[i]) w[i]&&!~D[to]&&(q.push(to),D[to]=D[u] 1);return ~D[T];}
I int Dfs(CI x,CI flow){if(x==T) return flow;RI now=flow,i,d;for(i=cur[x];i;i=nxt[i]) if(cur[x]=nxt[i],w[i]&&D[to]==D[x] 1){d=Dfs(to,min(now,w[i])),w[i]-=d,w[i^1] =d,now-=d;if(!now) break ;}return flow-now;}
I int Dinic(){RI i,X=0;W(Bfs()){for(i=1;i<=cnt;i ) cur[i]=fir[i];X =Dfs(S,inf);}return X;}
I void DFS(CI x){RI i;for(visR[x]=1,i=1;i<=n;i ) b[i][x]&&!visL[i]&&(visL[i]=1,DFS(r[i]),0);}
int main(){
freopen("isolated.in","r",stdin),freopen("isolated.out","w",stdout);
RI i,j,k,x,y;for(read(n,m),i=1;i<=m;i ) read(x,y),b[x][y]=1;
for(k=1;k<=n;k ) for(i=1;i<=n;i ) b[i][k]&&(b[i]=b[k],0);
for(S=1,cnt=(n<<11),T= cnt,i=1;i<=n;i ) Add(S,i<<1,1),Add(i<<11,T,1);
for(i=1;i<=n;i ) for(j=1;j<=n;j ) b[i][j]&&(Add(i<<1,j<<11,1),0);
Ans=n-Dinic(),writeln(Ans);
for(i=1;i<=n;i ) if(!w[i*4-2]) for(j=fir[i];j;j=nxt[j]) son[j]^S&&!w[j^1]&&(r[i]=son[j]/2);
for(i=1;i<=n;i ) if(w[i*4]) DFS(i);for(i=1;i<=n;i ) write(!visL[i]&&visR[i]);pc('n');
for(k=1;k<=n;write(gT-Dinic()==Ans-1),k ){
for(i=1;i<=n;i ) Mk[i]=(k^i&&!b[k][i]&&!b[i][k]);
for(memset(fir,0,sizeof(fir)),tot=S=1,gT=0,cnt=(n<<11),T= cnt,i=1;i<=n;i ) Mk[i]&&(Add(S,i<<1,1),Add(i<<11,T,1),gT );
for(i=1;i<=n;i ) for(j=1;j<=n;j ) Mk[i]&&Mk[j]&&b[i][j]&&(Add(i<<1,j<<11,1),0);
}return pc('n'),clear(),0;
}
