这次其实难度还行，也都是一些可以下手的题，但由于做的太少了，敲的代码太少，出了很多bug，一些细节也有些遗忘，例如bfs的vis标记在push时记录，等，同时由于参加的比赛少，有些紧张，第一道题卡了挺久，后面做得入迷了心态也好了些。

图，流，最短路

  • 完全图
  • 点与边的数量关系
  • 联通块，染色

A. Vasya and Isolated Vertices

 

要得到最少的孤立点，就需要每条边都连两个独立点，任意两条边无公共端点；

得到最多的孤立点，就需要尽量密集，尽量构造完全图，完全图上边数m,点数n，m=n(n−1)2m=\frac{n(n-1)}{2}，那么我们先用尽量多的边去构造完全图，找到n(n-1)/2<m的最大n，接下来可能还剩余一些边，那么我们再拿出一个孤立点，与完全图中所有点相连，可以证明只要拿出一个点就能用完所有剩余的边。

设已构造的完全图中有k个点，则有k(k-1)/2条边，我们再拿出一个点，最多与图中k个点都相连，则共有k(k−1)2+k\frac{k(k-1)}{2}+k条边，由于k(k−1)2+k−(k+1)k2=1>0\frac{k(k-1)}{2}+k-\frac{(k+1)k}{2}=1>0，所以k(k−1)2+k>(k+1)k2\frac{k(k-1)}{2}+k>\frac{(k+1)k}{2}，这说明如果我们连完图中所有k个点，总边数应该是大于下一个完全图的边数的，而这与我们第一步用尽可能多的边挑选完全图的前提相矛盾。所以结论是我们不可能连完k个点。

也就是说最多只需要再拿出1个点，就能用完剩余的边。

其实不推公式也可以理解，如果连完所有k个点，就相当于建了一个(k+1)个点的完全图，那我们为何不一开始就取k+1？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<algorithm>
#include<iostream>
using namespace std;
int main() {
	long long hashn[100005];
	long long n, m;
	cin >> n >> m;
	for (long long i = 1; i <= n; i++) {
		hashn[i] = (i - 1)*i / 2;
	}
	long long mn = max(0ll, n - 2 * m);
	long long mx;
	if (m == 0) {
		mx = n;
	}
	else {
		long long pos = lower_bound(hashn, hashn + n + 1, m) - hashn;
		mx = n - pos;
	}
	cout << mn << ' ' << mx;
	return 0;
}

 

B. Mouse Hunt

 

三种情况

  1. 房间指向自身，那么如果我们到达了这个房间就再也出不去了，那如果我们刚开始就在这个房间呢？所以这种房间是必须要放药的。

  2. 几个房间形成一个环，那么我们不论在那个房间都能去到环中任意房间，那么只需要找到环中最便宜的那个房间放药就好了。

    上述两种情况是必须要处理的，因为出生在其中就永远出不去了。

  3. 几个房间形成一条链，这么说是不完全的，因为链的末端要么是一个指向自身的端点，要么是一个环，也就是说链最终都会有1或2的情况，那么我们只需要在末端或环中处理，就相当于处理了一整个链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 2e5 + 5;
int n, c[maxn], a[maxn];
int ans;
int vis[maxn];
int par[maxn];
void visit(int s) {
	vis[s] = 1;
	int to = a[s];
	if (!vis[to]) {
		visit(to);
	}
	else if (vis[to] == 1) {
		if (to == s)ans += c[to];
		else {
			int mn = c[to];
			int tmp = a[to];
			while (tmp != to) {
				mn = min(mn, c[tmp]);
				tmp = a[tmp];
			}
			ans += mn;
		}
	}
	vis[s] = 2;
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i])
			visit(i);
	}
	cout << ans;
	return 0;
}

 

C. Jzzhu and Cities

 

Dijkstra

把所有（包含train路）的边存图，以1为起点存每个点的最短路。

对一个train，如果它的长度大于该点的最短路，直接删除；若等于最短路，如果最短路不止一条，删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<map>
#include<functional>
using namespace std;
#define ll long long
int n, m, k;
const int maxn = 1e5 + 200;
typedef pair<long, int> pii;
struct node {
	int to;
	int dis;
};
vector<node>G[maxn];
ll d[maxn];
bool vis[maxn];
void add_edge(int u, int v, int x) {
	G[u].push_back(node{ v,x });
	G[v].push_back(node{ u,x });
}
int s[maxn];
ll y[maxn];
priority_queue<pii, vector<pii>, greater<pii> >que;
int in[maxn];
void dij() {
	que.push(pii(0ll,1));
	while (!que.empty()) {
		pii tp = que.top();
		que.pop();
		int u = tp.second;
		if (vis[u])continue;
		vis[u] = 1;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].to, dis = G[u][i].dis;
			if (d[u] + dis < d[v]) {
				in[v] = 1;
				d[v] = d[u] + dis;
				que.push(pii(d[v],v));
			}
			else if (d[u] + dis == d[v])
				in[v]++;
		}
	}
}
int main() {
	cin.sync_with_stdio(false);
	memset(d, 0x3f, sizeof(d));
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int u, v, x;
		cin >> u >> v >> x;
		add_edge(u, v, x);
	}
	for (int i = 0; i < k; i++) {
		cin >> s[i] >> y[i];
		add_edge(1, s[i], y[i]);
	}
	d[1] = 0;
	dij();
	//cout << d[0];
	int ans = 0;
	for (int i = 0; i < k; i++) {
		if (y[i] > d[s[i]])ans++;
		else {
			if (d[s[i]]==y[i]&&in[s[i]] > 1) {
				ans++;
				in[s[i]]--;
			}
		}
	}
	cout << ans;
	return 0;
}

 

D. Igor In the Museum

 

和计算联通块差不多，主要是看到网上的写法很清爽，所以记一下。

用dfs算联通块

同时以询问编号为vis，记录下已经算好的一块答案，很巧妙的做法

我刚开始是想取块中某一个的坐标为染色标记，但因为二维坐标，还是没有用询问编号来的方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, k, qid;
char mz[1005][1005];
int ans[100005];
int vis[1005][1005];
int res;
void visit(int x, int y) {
	if (mz[x][y] == '*') {
		res++;
		return;
	}
	if (x<1 || x>n || y<1 || y>m) {
		return;
	}
	if (!vis[x][y]) {
		vis[x][y] = qid;
		visit(x - 1, y);
		visit(x + 1, y);
		visit(x, y - 1);
		visit(x, y + 1);
	}
}
int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mz[i][j];
		}
	}
	for (qid = 1; qid <= k; qid++) {
		int x, y;
		cin >> x >> y;
		if (vis[x][y]) {
			cout << ans[vis[x][y]] << endl;
			continue;
		}
		res = 0;
		visit(x, y);
		ans[qid] = res;
		cout << res << endl;
	}
	return 0;
}