[CTSC2008] 祭祀
一、题目
点此看题
最长反链：如果 \(u\) 存在路径到 \(v\)，那么 \(u,v\) 不能共存，满足这样条件的最大点集。
二、解法
这题好复杂一堆结论定理，但是这个模型还是真的挺常见的，把做法背住即可。
根据 \(\tt Dilworth\) 定理，\(\tt DAG\) 中最长反链的大小等于最小链覆盖的大小。
但是这个最小链覆盖是基于传递闭包的（也就是如果 \(x,y\) 之间有路径那么连边 \(x\rightarrow y\)），所以我们一开始要跑一遍 \(\tt floyd\) 求出传递闭包，然后在这个上面做最小链覆盖。
最小链覆盖的方法就是拆点二分图：我们把每个点拆成 \(x_{out},x_{in}\)，让他们分居左右两侧，如果存在边 \(x\rightarrow y\)，那么我们把 \(x_{out}\) 连向 \(y_{in}\)，那么最小链覆盖等于总点数减去最大匹配。
设点数是 \(n\)（二分图上的点数是 \(2n\)），最大匹配是 \(m\)
我们考虑用最大匹配构造二分图的最小点覆盖，构造方法是我们以右侧非匹配点开始 \(\tt dfs\)，右侧只能走非匹配边向左，左侧只能走匹配边向右。我们取左侧被 \(\tt dfs\) 到的点和右侧没有被 \(\tt dfs\) 到的点为集合 \(S\)，可以证明 \(S\) 是一个最小点覆盖。
我们分别证明 \(S\) 是大小是最小的，\(S\) 是一个点覆盖：
因为最小点覆盖等于最大匹配，所以我们只需要证明 \(|S|=m\) 即可说明 \(S\) 最小。考虑我们的构造对于每一条匹配边，它的两端恰好有一个点在 \(S\) 中。因为如果它被 \(\tt dfs\) 过，那么左侧的匹配点会在 \(S\) 中；否则它没有被 \(\tt dfs\) 过，那么右侧的点会在 \(S\) 中。并且 \(S\) 中只有匹配点，所以说 \(|S|=m\)
我们再证明 \(S\) 是一个点覆盖。只有左侧没有被 \(\tt dfs\) 到，并且右侧被 \(\tt dfs\) 到的边需要考虑，然而这种边是不存在的，因为和右侧被 \(\tt dfs\) 到的点相连的左侧点都一定被 \(\tt dfs\) 过。
因为最大独立集是最小点覆盖的补集，所以可以求出最大独立集 \(I\)
考虑所有满足 \(x_{in}\) 和 \(x_{out}\) 都在 \(I\) 中的点 \(x\) 构成最长反链 \(A\)，显然这东西是一个反链（由独立集的定义可以很容易得出），那么我们考虑证明它是最长的。
因为 \(|I|=2n-|S|=2n-m\)，而 \(|I|-|A|\) 可以看成满足 \(x_{out}/x_{in}\) 恰好一个属于 \(I\) 的 \(x\) 个数，所以有 \(|I|-|A|\leq n\Rightarrow |A|\geq n-m\)，根据 \(\tt Dilworth\) 定理又有 \(|A|\leq n-m\)，所以 \(|A|=n-m\) 是最长的。
那么 \(A\) 中的元素就是：左侧没有被 \(\tt dfs\) 到并且右侧被 \(\tt dfs\) 到的点。
对于第三问，我们尝试删除每个点和与其有路径关系的点，然后跑最大匹配，如果得到的最长反链只减小了 \(1\)，那么说明这个点是可能出现在最终答案中的，时间复杂度 \(O(n^3)\)
#include
#include
#include
#include
using namespace std;
const int M = 205;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,S,T,tot,f[M],cur[M],dis[M];
int ans,mat[M],tl[M],tr[M],del[M];
struct edge{int v,c,next;}e[M*M];bitset g[M];
void add(int u,int v,int c)
{
e[++tot]=edge{v,c,f[u]},f[u]=tot;
e[++tot]=edge{u,0,f[v]},f[v]=tot;
}
int bfs()
{
for(int i=S;i<=T;i++) dis[i]=0;
queue q;dis[S]=1;q.push(S);
while(!q.empty())
{
int u=q.front();q.pop();
if(u==T) return 1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dis[v] && e[i].c>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int ept)
{
if(u==T) return ept;
int flow=0,tmp=0;
for(int &i=cur[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1 && e[i].c>0)
{
tmp=dfs(v,min(ept,e[i].c));
if(!tmp) continue;
flow+=tmp;ept-=tmp;
e[i].c-=tmp;e[i^1].c+=tmp;
if(!ept) break;
}
}
return flow;
}
int dinic()
{
int res=0;
while(bfs())
{
for(int i=S;i<=T;i++) cur[i]=f[i];
res+=dfs(S,inf);
}
return res;
}
void work(int u)
{
tr[u]=1;
for(int i=1;i<=n;i++)
if(g[i][u] && !tl[i])
tl[i]=1,work(mat[i]);
}
signed main()
{
n=read();m=read();
S=0;T=2*n+1;tot=1;
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
g[x][y]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(g[i][k]) g[i]|=g[k];
//build the graph
for(int i=1;i<=n;i++)
add(S,i,1),add(i+n,T,1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]) add(i,j+n,1);
ans=n-dinic();
printf("%d\n",ans);
for(int i=1;i<=n;i++) if(!e[4*i-2].c)
//for the matched node
for(int j=f[i];j;j=e[j].next)
if(!e[j].c) mat[i]=e[j].v-n;
//dfs the right unmatched node
for(int i=1;i<=n;i++) if(e[4*i].c) work(i);
//x_in unvisited , x_out visited
for(int i=1;i<=n;i++) printf("%d",!tl[i]&&tr[i]);
puts("");
//test every node
for(int u=1;u<=n;u++)
{
for(int i=S;i<=T;i++) f[i]=0;
for(int i=1;i<=n;i++) del[i]=0;
del[u]=tot=1;int cnt=0;
for(int i=1;i<=n;i++)
if(g[u][i] || g[i][u]) del[i]=1;
for(int i=1;i<=n;i++) if(!del[i])
add(0,i,1),add(i+n,T,1),cnt++;
for(int i=1;i<=n;i++) if(!del[i])
for(int j=1;j<=n;j++) if(!del[j])
if(g[i][j]) add(i,j+n,1);
printf("%d",cnt-dinic()==ans-1);
}
puts("");
}