[洛谷 4298][CTSC2008]祭祀

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注