目录
显示
题目链接
https://www.luogu.org/problem/P4298
题解
Part 1
我们定义反链为一个点的集合，集合内的任意两点不能存在一条路径相连。
则可以证明：最长反链=最小链覆盖=点数-最大匹配数。
先跑一遍传递闭包，我们将点 \(i\) 拆成两个点 \(i,i+n\)，对于 \(x\) 能到达 \(y\) 的情况，连接一条 \(x\) 到 \(y+n\) 的路径。
然后跑一遍二分图最大匹配即可。
Part 2
第二问让我们构造一组二分图的最大独立集。
我们可以这样构造：每次从二分图左边的找一个没匹配的点，从左往右走的时候走匹配边，从右往左走的时候走非匹配边即可。
最后左边未访问的点和右边访问的点即为一组最大独立集。
r_64 在 uoj 上给出了该构造正确性的 证明 。
Part 3
第三问让我们求出哪些点可以成为最长反链的组成部分。
我们每次枚举一个点，删除它及与它相连的所有边，再求一次最长反链，如果最长反链变小，则该点是最长反链的一个组成部分。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,next;
}e[2000005];
int f[105][105],head[205],vis[205],cur[205],dep[205],s,t,cnt=1,n,m;
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
queue<int> q;
memcpy(cur,head,sizeof(cur));
memset(dep,INF,sizeof(dep));
dep[s]=0,vis[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next)
if(e[i].w&&dep[e[i].v]>dep[u]+1)
{
dep[e[i].v]=dep[u]+1;
if(!vis[e[i].v])
{
q.push(e[i].v);
vis[e[i].v]=1;
}
}
}
return dep[t]!=INF;
}
int dfs(int u,int w)
{
if(u==t)return w;
int used=0;
for(int i=cur[u];i;i=e[i].next)
{
cur[u]=i;
if(dep[e[i].v]==dep[u]+1&&e[i].w)
{
int flow=dfs(e[i].v,min(w,e[i].w));
if(flow)
{
used+=flow;
e[i].w-=flow;
e[i^1].w+=flow;
if(used==w)break;
}
}
}
return used;
}
int res[205];
void find(int u)
{
if(!res[u]&&u<=n)return;
if(res[u]&&u>n)return;
if(u<=n)
{
res[u]=0;
for(int i=head[u];i;i=e[i].next)
if(e[i].w)find(e[i].v);
}
else
{
res[u]=1;
for(int i=head[u];i;i=e[i].next)
if(!e[i^1].w)find(e[i].v);
}
}
int main()
{
//Initiation start
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
f[u][v]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
//Initiation end
//Part 1 start
s=2*n+1,t=2*n+2;
for(int i=1;i<=n;i++)
{
addedge(s,i,1);
addedge(i,s,0);
addedge(i+n,t,1);
addedge(t,i+n,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&f[i][j])
{
addedge(i,j+n,1);
addedge(j+n,i,0);
}
int ans=0;
while(bfs())
ans+=dfs(s,INF);
printf("%d\n",ans=n-ans);
//Part 1 end
//Part 2 start
for(int i=1;i<=n;i++)
res[i]=1;
for(int i=1;i<=n;i++)
if(e[4*i-2].w)find(i);
for(int i=1;i<=n;i++)
printf("%d",!(res[i]|res[i+n]));
puts("");
//Part 2 end
//Part 3 start
for(int i=1;i<=n;i++)
{
memset(head,0,sizeof(head));
cnt=1;
int cntp=0;
for(int j=1;j<=n;j++)
if(i!=j&&(!f[i][j])&&(!f[j][i]))
{
addedge(s,j,1);
addedge(j,s,0);
addedge(j+n,t,1);
addedge(t,j+n,0);
cntp++;
}
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(j!=k&&i!=j&&f[j][k])
{
addedge(j,k+n,1);
addedge(k+n,j,0);
}
while(bfs())
cntp-=dfs(s,INF);
printf("%d",ans-1==cntp);
}
//Part 3 end
return 0;
}