文章
68
粉丝
691
获赞
26
访问
578.4k
这实际上是一棵树,拓扑排序一下,关键点的流量是所有出水口的数目之和
#define ll int
#define vec vector<ll>
#define inf 0x3f3f3f3f
#define MAX 100005
int n, u, v, ind[MAX], flow[MAX];
vec G[MAX];
int main() {
while (cin >> n) {
memset(ind, 0, sizeof(ind));
memset(flow, 0, sizeof(flow));
for (int i = 0; i <= n; i++)G[i].clear();
for (int i = 0; i < n - 1; i++) {
cin >> u >> v;
G[u].push_back(v);
ind[v]++;
}
queue<int> q; int maxf = 0;
for (int i = 1; i <= n; i++)
if (ind[i] == 0) {
maxf++; q.push(i); flow[i] = 1;
}
while (!q.empty()) {
u = q.front(); q.pop(); int num = G[u].size();
for (int i = 0; i < num; i++) {
v = G[u][i];
flow[v] += flow[u] / num;
ind[v]--;
if (ind[v] == 0)
q.push(v);
}
}
for (int i = 1; i <= n; i++) {
if (flow[i] == maxf)
cout << i << endl;
}
}
}
登录后发布评论
暂无评论,来抢沙发