YbtOJ 574「二分图匹配」孤立点集

(Updated: )
oi
, ,

题目链接：YbtOJ #574

小 A 有一张 $n$ 个点 $m$ 条边的 DAG，他想要知道最多能选出多少个点，使得这些点中不存在某两个点满足 其中一个点能到达另一个点，并希望你给出任意一种点数最多的构造方案。

更进一步，他想要知道每个点是否 可能 出现在一种点数最多的构造方案中。

$1\le n\le100$，$1\le m\le 10^3$。

Solution

由 Dilworth 定理，一个 DAG 中最长反链的大小，等于其中最小可重链覆盖大小。

最小可重链覆盖：在 DAG 中选出若干条链，经过每个点至少一次，一个点可被一条链经过多次，且链数尽量少。

考虑将每个点拆成出点和入点，对于一条边 $x\rightarrow y$，连接 $x_o$ 与 $y_i$。

那么我们就可以在这个二分图 $G=\langle \langle V_o,V_i\rangle,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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+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;
}