Tutorial

神仙题

这个 $\frac47$ 似乎提示性很强的样子,不难想到拆成 $\frac{4}{1 + 2 + 4}$

这启示我们把点分为三个集合 $A, B, C$,满足限制 $|C| \leq 2|B| \leq 4|A|$,然后把 $C$ 集合中的点全部删除

考虑如何限制集合的大小关系,题目中保证一个点最多只有两条出边,那么如果我们有两个集合 $U,V$ 满足 $V$ 中的点都有一条来自 $U$ 的入边,就可以得到 $|V| \leq 2|U|$

按照这个思路,我们可以如下定义三个集合:

  • A: 没有入边或者所有入边来自 $C$
  • B: 至少有一条入边来自 $A$,没有入边来自 $B$
  • C: 至少有一条入边来自 $B$

不难证明一定能这样划分。

题目中给定的图是 DAG,所以可以直接按照拓扑序逐个确定。

Code

enum color_t
{
 color_a, 
 color_b,  
 color_c
};
enum color_t col[N];
void solve()
{
 scanf("%d%d", &n, &m);
 clear_graph();
 for (int i=0; i<m; ++i)
 {
   int u, v;
   scanf("%d%d", &u, &v);
   add_edge(v, u);
 }
 col[1] = color_a;
 for (int u=2; u<=n; ++u)
 {
   col[u] = color_a;
   for (struct edge_t *i = e[u]; i; i = i->next)
   {
     if (col[i->v] == color_b)
       col[u] = color_c;
     if (col[u] != color_c && col[i->v] == color_a)
       col[u] = color_b;
   }
 }
 int cnt = 0;
 for (int i=1; i<=n; ++i)
   if (col[i] == color_c)
     cnt++;
 printf("%d\n", cnt);
 for (int i=1; i<=n; ++i)
   if (col[i] == color_c)
     printf("%d ", i);
 puts("");
}



Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.