CF1062F Upgrading Cities

tony102

2021 年 02 月 27 日

1855 次浏览

暂无评论

829字数

题解

[Link](https://www.luogu.com.cn/problem/CF1062F)

## Sol

> 球：拓扑排序是一个黑箱操作是吧？就是你根本不知道它在干什么，但是我们可以想一想拓扑排序的“黑箱”有什么性质

拓扑排序的“黑箱”队列的性质，一个点能进队列，当且仅当他的前驱节点都已出队。在一张DAG上，若两个点同时出现在队列中，那么他们互相无法到达，否则不是DAG。因为两个点在没有环的前提下能互相到达，只能是从相同的前驱过来。能同时出现在队列中说明没有这样的前驱节点。

我们记 $f_i$ 表示从该点可以走到的点集和可以走到该点的点集的并集大小。分开处理该点可以走到的点和可以走到该点的点，只要建出反图做相同的操作即可。

以在正图上的情况做说明，反图的情况同理可得

先来算算重要节点。加入在一个队列里面，假如现在队列里面只有它一个点$i$，那么它可以到的点就是除它意外的所有$n-1$个点。这样对$f_i$的贡献就是$n-tot$ . $tot$ 指的是拓扑开始前就入队的点的个数。

那么次重要节点的计算也很简单。次重要节点要成为重要节点，当且仅当队列中元素个数为$2$时，设这两个点分别为$u,v$， 在$u$到$v$的路径上只要存在一个点的入度为$1$，那么这个点被删除之后这两个点中的任意一者即满足条件。把贡献记到任意一个点上，给另外一个点打上标记即可。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 3e5 + 5;

int n, m, num;
int head[SIZE], deg[SIZE], vis[SIZE], f[SIZE], cx[SIZE], cy[SIZE];

struct node {
	int to, nxt;
} edge[SIZE << 1];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void calc(int u, int to, int w) {
	int flag = 0;
	for (int i = head[to], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (deg[v] == 1) { flag = 1; break; }
	}
	if (flag) vis[u] = 1;
	else f[u] += w;
}

void top() {
	int cnt = 0;
	std::queue < int > q;
	for (int i = 1; i <= n; ++ i) {
		if (!deg[i]) q.push(i), ++ cnt;
	}
	while (!q.empty()) {
		int u = q.front(), siz = q.size(); q.pop();
		if (siz == 1) f[u] += n - cnt;
		else if (siz == 2) calc(u, q.front(), n - cnt);
		for (int i = head[u], v; i; i = edge[i].nxt) {
			v = edge[i].to, -- deg[v];
			if (!deg[v]) q.push(v), ++ cnt;
		}
	}
}

int main() {
	// freopen("code.in", "r", stdin);
	n = read(), m = read();
	for (int i = 1; i <= m; ++ i) {
		cx[i] = read(), cy[i] = read();
		addEdge(cx[i], cy[i]); ++ deg[cy[i]];
	}
	top();
	num = 0; memset(head, 0, sizeof(head)); memset(deg, 0, sizeof(deg));
	for (int i = 1; i <= m; ++ i) {
		addEdge(cy[i], cx[i]), ++ deg[cx[i]];
	}
	top();
	int res = 0;
	for (int i = 1; i <= n; ++ i) {
		if (!vis[i] && f[i] >= n - 2) ++ res;
	}
	printf("%d\n", res);
	return 0;
}
```

最后修改：2021 年 08 月 20 日