CF1019C Sergey's problem
很巧妙的构造题。
思路
首先我们可以把这题分成两个部分:
- 解决覆盖问题
- 解决边冲突问题
\(vis_i\) 为 \(i\) 点是否被覆盖的标记,\(cis_i\) 为 \(i\) 点是否被选的标记。
part1 覆盖问题
从小到大枚举 \(i\),对于点 \(i\) 如果它没被覆盖,那么我们把点 \(i\) 标为被覆盖并且使这个点被选中,存在有向边 \(i->j\) 的 \(j\) 标为被覆盖。
part2 冲突问题
从大到小枚举 \(i\),对于点 \(i\) 如果它被选中,那么我们把这个点 \(i\) 存在有向边 \(i->j\) 的点 \(j\) 的选中标记去掉。
这样的答案就是一组合法答案。
证明:
第一个部分,满足了被选中点存在边冲突当且仅当 \(u>v\) 且存在边 \(u->v\) 不存在边 \(v->u\)。
第二个部分,证明:一个点进行了二部分的操作后一定会被留下。
设点 \(u\) 进行完二部分操作后被删除,不妨设删除 \(u\) 的点为 \(v\),那么肯定有 \(u>v\) 且存在边 \(v->u\),与第一部分保证的情况产生冲突,故得证。
\(u\) 删除产生冲突的点后,对于产生冲突的点所覆盖的点,\(u\) 一定可以覆盖到(覆盖距离是 \(2\))。
易得经过一部分后所有的点都已处于被覆盖或被选中的状态,所有经过操作二后,所有的点亦处于被选中或被覆盖的状态。
得证。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct Edge
{
int tot;
int head[maxn];
struct edgenode{int to,nxt;}edge[maxn*2];
inline void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
}G;
int n,m,tot;
bool vis[maxn],cis[maxn];
inline void solve1(int u)
{
vis[u]=true;cis[u]=true;
for(int i=G.head[u];i;i=G.edge[i].nxt)
{
int v=G.edge[i].to;
vis[v]=true;
}
}
inline void solve2(int u)
{
for(int i=G.head[u];i;i=G.edge[i].nxt)
{
int v=G.edge[i].to;
cis[v]=false;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G.add(x,y);
}
for(int i=1;i<=n;i++) if(!vis[i]) solve1(i);
for(int i=n;i;i--) if(cis[i]) solve2(i);
for(int i=1;i<=n;i++) if(cis[i]) tot++;
printf("%d\n",tot);
for(int i=1;i<=n;i++) if(cis[i]) printf("%d ",i);
}
标签:head,覆盖,int,CF1019C,Sergey,edge,maxn,tot,problem
From: https://www.cnblogs.com/binbinbjl/p/18196941