网站设计制作公司,什么软件可以找做网站的,中国纪检监察报简介,仿京东网站后台problem
CF1368E Ski Accidents
solution
这个 47n\frac 47n74n 的限制#xff0c;提示这存在一个特定构造方案#xff0c;由 777 我们联想到 124712471247。
暗示把顶点分为三类 A,B,CA,B,CA,B,C#xff0c;满足 ∣C∣≤2∣B∣≤4∣A∣|C|\le 2|B|\le 4|A|∣C∣≤2∣…problem
CF1368E Ski Accidents
solution
这个 47n\frac 47n74n 的限制提示这存在一个特定构造方案由 777 我们联想到 124712471247。
暗示把顶点分为三类 A,B,CA,B,CA,B,C满足 ∣C∣≤2∣B∣≤4∣A∣|C|\le 2|B|\le 4|A|∣C∣≤2∣B∣≤4∣A∣。
此时 CCC 组的元素数目一定 ≤47n\le \frac{4}{7}n≤74n。
构造方式把所有入度为 000 的点都放入 AAA把至少有一条入边来自 AAA 但没有来自 BBB 的入边的点放入 BBB。然后把至少有一条入边来自 BBB 的入边的点放入 CCC。剩下的点所有入边都来 CCC 放入 AAA。
此时各类包含的顶点要求为
A:A:A: 入度为 000所有入边都来自 CCC。B:B:B: 至少有一条入边来自 AAA但没有来自 BBB 的入边。C:C:C: 至少有一条入边来自 BBB。
不难发现三类形成了一个有效的集合划分。
且因为每个点的出度都不超过 222即 AAA 的出边至多有 2∣A∣2|A|2∣A∣ 条所以 2∣A∣≥∣B∣2|A|\ge |B|2∣A∣≥∣B∣2∣B∣≥∣C∣2|B|\ge |C|2∣B∣≥∣C∣ 同理。
此时将 CCC 类点尽数删除。
由于 A,BA,BA,B 都没有来自 BBB 的入边而 AAA 内部点之间也不存在边所以一定不存在长度超过 111 的路径。
有向无环图所以可以在 O(n)O(n)O(n) 的时间内完成求解。
code
#include bits/stdc.h
using namespace std;
#define maxn 200005
vector int G[maxn], ans;
int T, n, m;
int col[maxn];int main() {scanf( %d, T );while( T -- ) {scanf( %d %d, n, m );for( int i 1;i n;i ) G[i].clear(), col[i] 0;for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );G[v].push_back( u );}for( int v 1;v n;v )for( int u : G[v] ) {if( col[u] 1 )col[v] 2;if( col[v] ^ 2 and col[u] 0 )col[v] 1;}ans.clear();for( int i 1;i n;i )if( col[i] 2 ) ans.push_back( i );printf( %d\n, ans.size() );for( int i : ans ) printf( %d , i );puts();} return 0;
}
