文章

68

粉丝

691

获赞

26

访问

578.4k

头像
拓扑排序
P1466
发布于2020年5月25日 19:06
阅读数 6.6k

这实际上是一棵树,拓扑排序一下,关键点的流量是所有出水口的数目之和

#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;
		}
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发