admin管理员组文章数量:1612828
C h o c o l a t e M i l k Chocolate Milk ChocolateMilk
传送门
思路
好的,先看数据,
-
对于40%的数据: 2 ≤ N ≤ 250 2≤N≤250 2≤N≤250;
-
对于50%的数据: 2 ≤ N ≤ 6 , 000 2≤N≤6,000 2≤N≤6,000;
-
对于100%的数据: 2 ≤ N ≤ 100 , 000 2≤N≤100,000 2≤N≤100,000; 1 ≤ A i < B i ≤ N 1≤A_i<B_i≤N 1≤Ai<Bi≤N;
暴力显然
拓扑排序
值得注意的是,这不是一棵树吗?
FJ发现对于牛奶来说有一种最多的方式从一个接口流到另一个接口。并且由于FJ是一个高效率的人,他需要确保每一个
管道都有牛奶经过,也就是说,没有多余的管道。
所以,对于牛奶来说,最多只有一种方式从一个接口流到另一个接口。则不会有牛奶分开
又聚到一起,故有一个性质:除非节点的入度 = 0 =0 =0 ,否则任何出度 > 1 >1 >1 的节点的子节点都
不能放置混合器。
a n s [ i ] ans[i] ans[i] 表示 如果在 i i i 结点造一个巧克力混合器,最多能经过的牛奶数(每个点初始为 1 1 1 )
用拓扑排序遍历整棵树,并累加上一个结点的 a n s [ u ] ans[u] ans[u]
- 只需要找到入度为 0 0 0 的结点,标记(后面有用),并放入队列
for (int i = 1; i <= n; i++)
if (!ind[i])
q.push(i), ans[i] = check[i] = 1, cnt++;
- 每次找孩子只需要找出度为 1 1 1 的结点(树)
对于每个点如果它的出度>1,那么他所连的边就不可能成为巧克力混合器
- 对于每个结点 x x x ,若其 a n s [ i ] ans[i] ans[i] 值为总边数,且入度不为 0 0 0 ,不为 0 0 0 (上面说过)
A C c o d e AC code ACcode
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 99;
int n, m, t, tot, cnt;
int head[maxn], out[maxn], ind[maxn];
int ans[maxn];
bool check[maxn];
struct Edge
{
int to, next;
} e[maxn];
void add(int a, int b)
{
e[++tot].to = b;
e[tot].next = head[a];
head[a] = tot;
}
void init()
{
tot = 0;
cnt = 0;
memset(head, 0, sizeof(head));
memset(ind, 0, sizeof(ind));
}
void topo()
{
queue<int> q;
for (int i = 1; i <= n; i++)
if (!ind[i])
q.push(i), ans[i] = check[i] = 1, cnt++;
while (!q.empty())
{
int tmp = q.front();
q.pop();
if (out[tmp] == 1)
{
int j = head[tmp];
ans[e[j].to] += ans[tmp];
if (--ind[e[j].to] == 0)
q.push(e[j].to);
}
}
}
int main()
{
init();
cin >> n;
for (int i = 1, a, b; i < n; i++)
{
cin >> a >> b;
add(a, b);
out[a]++;
ind[b]++;
}
topo();
for (int i = 1; i <= n; i++)
{
if (ans[i] == cnt && !check[i])
{
cout << i << endl;
}
}
}
版权声明:本文标题:Chocolate Milk(洛谷P2999) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1727269284a1105824.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论