Post

暑期集训图论

Posted Updated
By Akejyo 53 min read

图论

A. 蜘蛛的网

题意：给定一个无向连通图，求至少要去掉几条边才能使图不连通，即求无向连通图的最小割

Stoer-Wagner 算法

关于算法的证明： Stoer-Wagner 算法 - OI Wiki (oi-wiki.org)

算法流程:

  • 在图G中确定一点S，每次把S的邻居中边权最大的那个邻居与S合并，更新边和边权。

image-20240503135518836

  • 2作为我们确定的S，他的邻边里与3连的边是最大的，所以把3与2合并，并把3的边(蓝色的边)更新。image-20240503135546644

  • 反复这样操作到最后两次，我们需要保存除S的最后两个点，在该轮操作完成后在原图里把1,5合并。

image-20240503135601624

  • 继续操作，用最后留下的边更新ans。

image-20240503135608728

  • 在原图里合并1、5，继续上述操作直到原图无法操作，每轮操作都能更新一下ans。

image-20240503135613857

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

int sp[1010][1010];
int w[1010];
int vis[1010];
int mer[1010];//是否已被合并
int n;
int x, y;
int merge() {
	int i;
	memset(vis, 0, sizeof(vis));
	memset(w, 0, sizeof(w));
	int an = 1e9;
	x = 0, y = 0;
	int flag = 0;
	while (1) {
		int M = -1, M_dex = 0;
		for (i = 1; i <= n; i++) {
			if (!vis[i] && !mer[i] && w[i] > M) {
				M = w[i];
				M_dex = i;
			}
		}
		vis[M_dex] = 1;
		if (M_dex == 0) {
			if (flag>1)
				return an;
			else
				return 1e9;
		}//结束，此时an为最后一个没被合并的
		an = M;
		x = y, y = M_dex;//更新一下，在当前函数结束后用来合并原数组
		for (i = 1; i <= n; i++)
			if (!vis[i] && !mer[i])
				w[i] += sp[i][M_dex];//合并合并合并
		flag++;
	}
}
void solve() {
	int i, j;
	int m;
	sii(n, m);
	for (i = 0; i < m; i++) {
		int t1, t2;
		sii(t1, t2);
		sp[t1][t2]++;
		sp[t2][t1]++;
	}
	int tem = n - 1;
	int ans = 1e9;
	while (tem--) {
		ans = mmm(ans, merge());
		mer[y] = 1;
		for (i = 1; i <= n; i++) {//合并原数组
			if (!mer[i]) {
				sp[i][x] += sp[i][y];
				sp[x][i] += sp[y][i];
			}
		}
	}
	printf("%d", ans);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

C .魔法少女

题意: 矩形网格里，只能沿对角线移动，每个格子只有一个对角线是通路（通过的代价是0），另一个对角线通过需要1代价。求从左上角移动到右下角最少花费（或不能做到）。

矩形图上 Dijkstra

很容易就能想到用最短路的方法去解，可以直接建图：以网格图上的点为节点，每个点至多能连4个边（与左上、左下，右上，右下相连），权值为1或0，然后跑一遍$Dijkstra$就行。

BUT这种矩形网格图建图属实是没必要，每个点的邻居都是确定的，联想到走迷宫类的题，我们可以用两个数组来操控魔法少女的x,y坐标。

1
2

int dx[4] = { 1,1,-1,-1 };
int dy[4] = { 1,-1,-1,1 };

这样遍历$dx,dy$,魔法少女的下一个坐标就为$x+dx[i],y+d[y]$。同时再用两个数组来表示一个点所连的格子的坐标。

1
2

int dor_x[4] = { 0,0,-1,-1 };
int dor_y[4] = { 0,-1,-1,0 };

$x+dor_x[i]$和$y-dor_y[i]$即为四个格子的坐标。 image-20240503135722496

其余的就是稍微改改$Dijkstra$的板子就行。

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

int dis[510][510];//到起点距离
int dx[4] = { 1,1,-1,-1 };
int dy[4] = { 1,-1,-1,1 };
int dor_x[4] = { 0,0,-1,-1 };
int dor_y[4] = { 0,-1,-1,0 };
bool vis[510][510];
char door[510][510];
int cut, n, m;
struct edge {
	int x, y, dis;
	friend bool operator < (edge a, edge b) { return a.dis > b.dis; }
};
priority_queue <edge> e;
void dfs(int n, int m) {//l记录长度
	int i;
	while (!e.empty()) {
		int x = e.top().x, y = e.top().y;
		e.pop();
		if (!vis[x][y]) {
			vis[x][y] = true;
			for (i = 0; i < 4; i++) {//这里是邻居们 (
				int tx = x + dx[i], ty = y + dy[i];
				if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) {
					if (!vis[tx][ty]) {
						int len;
						if ((dx[i] == dy[i] && door[x + dor_x[i]][y + dor_y[i]] == '/') || (dx[i] != dy[i] && door[x + dor_x[i]][y + dor_y[i]] == 92))
							len = 1;
						else
							len = 0;
						if (dis[x][y] + len < dis[tx][ty]) {
							dis[tx][ty] = dis[x][y] + len;
							e.push({ tx,ty,dis[tx][ty] });
						}
					}
				}
			}
		}
	}
}
void solve() {
	sii(n, m);
	memset(dis, 63, sizeof(dis));
	dis[n][m] = 0;
	for (int i = 0; i < n; i++)
		scanf("%s", door[i]);
	if (door[n - 1][m - 1] == '/')
		cut++;
	e.push({ n,m,0 });
	dfs(n, m);
	if (dis[0][0] > 1e9)
		printf("NO SOLUTION");
	else
		printf("%d", dis[0][0]);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

F. 开会了

题意：给定一组约束条件 $a_u-a_v <= w_i$，问是否存在一组$a_i$同时满足所有约束条件。

$a_u-a_v <= w_i$可以转化成$a_u<= w_i+a_v$ ，这就和跑最短路里$dist[y] <= dist[x] + z$ 很相似。所以我们只要按照 $a_v –w_i—>a_u$，建图跑最短路，看是否存在负环。如果有负环，$a_i$ 一直减减减就没个头了，也就是满足不了要求。

关于判断图里是否有负环，可以用 Bellman-Ford 算法

Bellman-Ford 算法找负环

算法流程： 对每个边$(u,v)$ ，$dis(v) = min(dis(v),dis(u)+w(u,v))$（dis(i)是i点到原点最短距离），称为松弛操作。我们不断对图上的每一条边进行松弛操作，当一轮遍历没有出现松弛操作时停止算法。显然每遍历一次图会至少增加一个最短路的边数，也就是说，最多遍历图n（点的个数）次。如果跑了n次以后算法还没结束，则可判断出现了负环。

Bellman-Ford可以用队列优化（SPFA)，但是该题好像不需要~

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

int vis[5010];
struct road {
	int v;
	int val;
};
vector<road> r[5010];
int d[5010];
void dfs(int u) {
	if (vis[u])
		return;
	vis[u] = 1;
	for (auto it : r[u])
		dfs(it.v);
}
int bellmanford(int n) {
	int i, flag = 0;//flag用来判断是否发生松弛
	for (i = 0; i < 5010; i++) d[i] = 1e9;
	d[0] = 0;
	for (i = 0; i <= n; i++, flag = 0) {
		for (int u = 0; u <= n; u++)
			for (auto it : r[u])
				if (d[it.v] > d[u] + it.val) {
					d[it.v] = d[u] + it.val;
					flag++;
				}
		if (!flag)
			break;
	}
	return i;
}
void solve() {
	int i, j;
	int n ,m, s;
	sii(n, m);
	for (i = 0; i < m; i++) {
		int a, b, c;
		siii(a, b, c);
		r[b].push_back({ a , c });//b->a
	}
	dfs(1);
	for (i = 1; i <= n; i++)//先dfs一波看看是否联通
		if (!vis) {
			printf("NO");
			return;
		}
	for (i = 0; i <= n; i++)//超级源点
		r[0].push_back({ i,0 });
	if (bellmanford(n) == n + 1)//最大是n,n+1就是负环
		printf("NO");
	else
		printf("YES");
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

I. 又开会了

题意: 给定m个约束条件，每个约束条件有u,x,v,y，表示$a_u=x$或$a_v=y$至少有一个成立（其中x,y为0或1）。问是否存在一组$a$同时满足所有约束条件。

$a_u=x$或$a_v=y$至少有一个成立，即$a_u=x$和$a_v=y$的非是矛盾的，直接把约束条件改成$a_u=x$和$a_v=y$矛盾，把$a_u=x$的非与$a_v=y$建边，$a_v=y$的非与$a_u=x$建边，然后跑$Tarjan$将各各点分成强连通分量，在每一个强连通分量里查询$a_u=0$和$a_u=1$是否同时出现，没有同时出现就是合理的。

虽然但是，再看这个建图感觉还是有点不妥，因为似乎没考虑同时为非的情况，但题ac了就不管了。

Tarjan

算法流程：

先对图跑$dfs$，对每个节点$u$维护两个变量：

  1. $dfn_u$：$u$在$dfs$中被第一次搜索的次序
  2. $low_u$：$u$在不经过其父节点的情况下能到达的$dfn$最小值

对于一个节点$u$，先把$u$压到栈里存起来，在处理他的邻居$v$时：

  1. 若$v$没有被访问过，先继续跑$dfs$，得到$low[v]$，因为$v$能回溯到的点$u$一定也行，所以$low[u]=min(low[u],low[v])$
  2. 若$v$已被访问过且$v$还没有确定其是属于哪个强连通分量，则$low[u]=min(low[u],dfn[v])$

若$dfn[u]=low[u]$，则栈里$u$及其上面的点合成一个强连通分量。

最后，对于一个强连通分量，将其中的点存到$set$里，对每个点查询$set$里是否有它的非，用$set$是因为$set$高贵的二分查找比较方便。

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
76
77
78
79
80
81
82

struct edge {
	int v;
	int val;
};
vector<edge> e[2 * MAX];
vector<int> S[2 * MAX];
set<int> S_name;//scc种类
int dfn[2 * MAX], low[2 * MAX];
int path[100000000];
int jg[MAX];
bool ins[2 * MAX];
int scc[2 * MAX];
int cut = 1;//cut是遍历次序
int sut = 0;//scc数量
int tp;
void tarjan(int u) {
	dfn[u] = cut; 
	low[u] = cut++;
	path[++tp] = u;
	ins[u] = true;
	for (auto it : e[u]) {
		int v = it.v;
		if (!dfn[v]) {//正常子节点（树边）
			tarjan(v);
			low[u] = mmm(low[u], low[v]);
		}
		else if(ins[v])
			low[u] = mmm(low[u], dfn[v]);//回到当前祖先去了
	}
	if (dfn[u] == low[u]) {
		while (path[tp] != u) {
			scc[path[tp]] = u;
			ins[path[tp--]] = false;
		}
		scc[path[tp]] = u;
		ins[path[tp--]] = false;
	}
}
void solve() {
	int i, j;
	int n, m, s;
	sii(n, m);
	for (i = 1; i <= m; i++) {
		int u, x, v, y;
		sii(u, x); sii(v, y);
		if (u != v) {//2i和2i+1分别是0和1 //至少有一个成立,即两者的“非”矛盾，就把条件当成是两者矛盾了
			if(y == 1)
			    e[2 * u + x].push_back({ 2 * v,1 });
			else
				e[2 * u + x].push_back({ 2 * v + 1,1 });
			if(x == 1)
			    e[2 * v + y].push_back({ 2 * u,1 });
			else
				e[2 * v + y].push_back({ 2 * u + 1,1 });
		}
	}
	int len = 2 * n + 1;
	for (i = 2; i <= len; i++)//要保证都循环了
		if (!dfn[i]) tarjan(i);
	for (i = 2; i <= len; i++) {
		S[scc[i]].push_back(i);
		S_name.insert(scc[i]);
	}
	for (auto it : S_name) {
		memset(jg, 0, sizeof(int)*(n+1));
		for (auto tp : S[it])
			if (jg[tp/2]) {
				printf("NO");
				return;
			}
			else
				jg[tp/2]++;
	}
	printf("YES");
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

J. tarjan

题意：求无向简单图的割点，割边，极大点双连通分量，极大点双连通分量包含边数的最大值

Tarjan

  • 先解决点双的问题

    跑$dfs$确定$dfn$和$low$($I$题里有)，对于节点$u$，在跑它的邻居的时候，只要这个邻居$v$没跑过就把$u-v$这条边压入栈内，当遇到$low[v] >= dfn[u]$时（这不一定是割点），把栈内的边一直弹出到$u-v$($u-v$不弹)，弹出的这些点构成了一个点双。把这些点存到一个$set$里，针对$set$里的这些点跑$dfs$来确定这个点双的边数，同时更新最大边数。

  • 然后是割点和割边，上面已经跑完了$dfs$，$dfn$和$low$都确定好了，再来一次$dfs$就行。对于割点，根节点的判断要注意一下，根必须要有至少两个子树才能作为割点（1 2; 2 3; 3 1.根只有一个子树，不是割点），非根节点只要有$low[v]>=dfn[u]$就可确定u是割点，v可以回溯到比u还远的位置（或者就是），那显然u就是割点。对于割边$low[v]>dfn[u]$就行。

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

vector<int> e[500000];
int dfn[1010], low[1010];
int vis[1010];
int cut;
int gedian, gebian;//割点割边数量
int re[1010];//记录割点
int ge_cut, ge_max = 0, gege ;//极大点双数量，最多边，cut
int flag;
stack<int> fir;
stack<int> sec;
set<int> mer;
int vis_s[1010];
void dfs_s(int u) {
	if (!vis_s[u])
		vis_s[u] = 1;
	for (auto v : e[u]) {
		if (mer.find(v) != mer.end()) {
			gege++;
			if (!vis_s[v])
				dfs_s(v);
		}
	}
}
void tarjan(int u, int fa) {
	dfn[u] = ++cut;
	low[u] = cut;
	for (auto v : e[u]) {
		if (!dfn[v]) {
			fir.push(u);
			sec.push(v);
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {//遇到割点
				mer.clear();
				ge_cut++;
				gege = 0;
				int temx, temy;
				do {
					temx = fir.top();
					temy = sec.top();
					mer.insert(temx);
					mer.insert(temy);
					fir.pop();
					sec.pop();
				} while (temx != u || temy != v);
				memset(vis_s, 0, sizeof(vis_s));
				dfs_s(u);
				gege /= 2;
				ge_max = max(ge_max, gege);
			}
		}
		else if (v != fa)//判断是否是它爸，不能是爸（
			low[u] = min(dfn[v], low[u]);
	}
}
void gegege(int u, int root) {
	vis[u] = 1;
	int s_tree = 0;//子树数量
	for (auto v : e[u]) {
		if (!vis[v]) {
			s_tree++;
			if (low[v] >= dfn[u]) {
				if (u != root) {// 要特判一下根处
					if (!re[u]) {
						gedian++;
						re[u] = 1;
					}
				}
				else if (s_tree >= 2) {
					if (!re[u]) {
						gedian++;
						re[u] = 1;
					}
				}
			}
			if (low[v] > dfn[u])
				gebian++;
			gegege(v, root);
		}
	}
}
void solve() {
	int n, m;
	sii(n, m);
	for (int i = 0; i < m; i++) {
		int u, v; sii(u, v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i, i);
			gegege(i, i);
		}
	}
	printf("%d %d %d %d", gedian, gebian, ge_cut, ge_max);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

K. 居民们都住在房屋里

题意：一个无向连通图，求任意两点之间的最近距离。

因为询问距离的次数会很多，肯定不能它问一次你跑一次最短路，需要对图进行预处理。

先随便弄给点当根节点，如果我们能知道所有点的深度$deep[i]$，那么两个点$u$和$v$之间的距离即为$deep[u]+deep[v]-2*deep[LCA(u,v)]$，其中$LCA(u,v)$为$u$和$v$的公共祖先。

LCA

  • 深度可以用$bfs$求，每求一层深度加一。

  • 可以选择暴力求公共祖先，对于$u$和$v$两个点，每次更新更深的那一个

1
2
3
4
5
6
7
8
9

int getlca(int a, int b) {
	while (a != b) {
		if (deep[a] > deep[b])
			a = fa[a];
		else
			b = fa[b];
	}
	return a;
}

该题的数据似乎没卡这种暴力，如果卡的话可以利用倍增算法：

最近公共祖先 - OI Wiki (oi-wiki.org)

用$fa_{x,i}$表示x的第$2^i$个祖先。先将u，v调整到同一深度得到u，v的深度差$y$，将$y$二进制拆分，第y次游标跳转优化成y的二进制中1的个数。之后，从最大的i开始循环尝试，一直尝试到0，若$fa_{u,i}\neq fa_{v,i}$，更新u为$fa_{u,i}$，v为$fa_{v,i}$，最后得到LCA为$fa_{u,0}$。

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

struct edge {
	int v;
	int val;
};
//vector<edge> e[5010];
int deep[500010];
int fa[500010];
bool vis[500010];
vector <int> T[500010];
queue<int> Q;
int getlca(int a, int b) {
	while (a != b) {
		if (deep[a] > deep[b])
			a = fa[a];
		else
			b = fa[b];
	}
	return a;
}
void ask() {
	int a, b;
	sii(a, b);
	int lca = getlca(a, b);
	printf("%d\n", deep[a] + deep[b] - 2 * deep[lca]);
}
void bfs(int u) {
	while (!Q.empty()) Q.pop();
	Q.push(u);
	vis[u] = true;
	deep[u] = 0;
	while (!Q.empty()) {
		u = Q.front();
		Q.pop();
		for (auto it : T[u]) {
			if (!vis[it]) {
				Q.push(it);
				vis[it] = true;
				deep[it] = deep[u] + 1;
				fa[it] = u;
			}
		}
	}
}
void solve() {
	int i, j;
	int n, m, s;
	sii(n, m);
	for (i = 1; i <= n - 1; i++) {
		int a, b;
		sii(a, b);
		T[a].push_back(b);
		T[b].push_back(a);
	}
	fa[1] = fa[1];
	bfs(1);
	while (m--)
		ask();
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

L. 最小生成树

题意：给定一个无向图，求最小生成树的个数

前提定理：对于一个图的最小生成树，其一种权边的数量是确定的。

  • 暴力

    将边按权值排序后得到$bian[i]$，同一种权边记录它的左端点$l$和右端点$r$，并标号。然后跑$Kruskal$算法，同时记录各种权边的数量。最后对于每一种权边，穷举满足权边数量的跑法（从$l[i]$跑到$r[i]$）与当前的$ans$相乘。TLE了哈哈

  • 矩阵树

    利用矩阵树定理来求当前图的生成树数量：邻边矩阵A(值为1)，度数矩阵D，其实度数矩阵：若有边(u,v,w),

    $D[u][u] = u$的度数，$D[v][v] = v$的度数，然后搭基尔霍夫矩阵$K = D - A$，该矩阵去掉任意一行任意一列后求行列式即为生成树数量。

    对于一种最小生成树的权边，把不同于该权值的边构成对应的连通块并缩成一个点

    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

    void sohard() {//处理一波权边
	for (auto it : point) 
		block[gf2(it)].push_back(it);//把点塞到它的连通块里
	point.clear();
	int num;
	for (int i = 1; i <= n; i++) 
		if ( (num = block[i].size()) > 1) {//大于一才有处理的必要
			memset(D, 0, sizeof(D));
			for(int j = 1; j <= num; j++)
				for (int k = j + 1; k <= num; k++) {
					int tem = A[block[i][j - 1]][block[i][k - 1]];
					if (tem) {//这里是基尔霍夫矩阵
						D[j][k] -= tem;
						D[k][j] -= tem;
						D[j][j] += tem;
						D[k][k] += tem;
					}
				}
			an = an * haoex(num - 1) % MOD;
			for (int j = 1; j <= num; j++)//把block[i]的点都归到 i
				fa[block[i][j - 1]] = i;
		}
	for (int i = 1; i <= n; i++) {//fa, fa2都连成连通块
		block[i].clear();
		fa[i] = gf(i);
		fa2[i] = gf(i);
	}
}

    1
2
3
4
5
6
7
8
9
10
11
12
13

    for (int i = 1; i <= m; i++) {
		if (e[i].w != e[i - 1].w)
			sohard();
		if ((x = gf(e[i].u)) != (y = gf(e[i].v))) {
			point.insert(x);
			point.insert(y);//point来记录当前长度的权边哪些连通块是要的，会在sohard里处理
			A[x][y]++;
			A[y][x]++;
			fa2[gf2(x)] = gf2(y);//合了
  			
		}
	}
	sohard();

    在生成的新图里求生成树的个数与ans相乘。

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

struct edge {
	int u, v, w;
};
int cut, cut2, an = 1;
int n,m,fa[10010] ,fa2[10010];//fa是合并前这个点所属连通块，fa2是合并后
int A[110][110], D[110][110];//A是邻接矩阵,D是基尔霍夫矩阵
set<int> point;
vector<int> block[1010];//记录连通块 block[连通块][里面的点......]
edge e[1010];
void s_k(int n, int* f) { for (int i = 1; i <= n; i++) f[i] = i; }//初始化f[]
int gf(int x) { return fa[x] == x ? x : gf(fa[x]); }//查连通块
int gf2(int x) { return fa2[x] == x ? x : gf2(fa2[x]); }
bool cmp(edge a, edge b) { return a.w < b.w; }
int haoex(int n) {//算行列式（
	int ans = 1;
	for (int i = 1; i <= n; i++) 
		for (int j = i + 1; j <= n; j++) {
			while (D[j][i]) {
				int x = D[i][i] / D[j][i];
				for (int k = i; k <= n; k++) {
					D[i][k] = (D[i][k] - (D[j][k]  * x % MOD) + MOD) % MOD;
					swap(D[i][k], D[j][k]);
				} ans *= -1;
			}
		}
	for (int i = 1; i <= n; i++) ans = (ans * 1ll * D[i][i]) % MOD;
	return (ans % MOD + MOD) % MOD;
}
void sohard() {//处理一波权边
	for (auto it : point) 
		block[gf2(it)].push_back(it);//把点塞到它的连通块里
	point.clear();
	int num;
	for (int i = 1; i <= n; i++) 
		if ( (num = block[i].size()) > 1) {//大于一才有处理的必要
			memset(D, 0, sizeof(D));
			for(int j = 1; j <= num; j++)
				for (int k = j + 1; k <= num; k++) {
					int tem = A[block[i][j - 1]][block[i][k - 1]];
					if (tem) {//这里是基尔霍夫矩阵
						D[j][k] -= tem;
						D[k][j] -= tem;
						D[j][j] += tem;
						D[k][k] += tem;
					}
				}
			an = an * haoex(num - 1) % MOD;
			for (int j = 1; j <= num; j++)//把block[i]的点都归到 i
				fa[block[i][j - 1]] = i;
		}
	for (int i = 1; i <= n; i++) {//fa, fa2都连成连通块
		block[i].clear();
		fa[i] = gf(i);
		fa2[i] = gf(i);
	}
}
void solve() {
	sii(n, m);
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		siii(a, b, c);
		e[i] = { a,b,c };
	}
	sort(e + 1, e + m + 1, cmp);
	e[0] = e[1];
	int x, y;
	s_k(n, fa);
	s_k(n, fa2);
	for (int i = 1; i <= m; i++) {
		if (e[i].w != e[i - 1].w)
			sohard();
		if ((x = gf(e[i].u)) != (y = gf(e[i].v))) {
			point.insert(x);
			point.insert(y);//point来记录当前长度的权边哪些连通块是要的，会在sohard里处理
			A[x][y]++;
			A[y][x]++;
			fa2[gf2(x)] = gf2(y);//合了
			
		}
	}
	sohard();
	for(int i = 2;i<=n;i++)
		if (fa[i] != fa[i - 1]) {
			printf("%d", 0);
			return;
		}
	printf("%d", an);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

O. 纯白色的少年郎，如今只身在何方

题意：给定一个有向图，求每个点到起点的最短路径。

因为$Dijkstra$在求最短路的过程中会不断更新每个节点到起点的最短距离，处理该问题相当合适。

Dijkstra

普通的$Dijstra$会$TLE(O(n^2))$，使用优先队列优化$(O(m log m))$。

算法流程：

  • 先初始化每个点到原点的最短距离$dis[i]$设为INF，将起点$dis[1]$设为0。

  • 将起点推入优先队列r中（按照$dis$从小到大排序）。只要r不空，执行下面操作：

    1. 弹出顶层u
    2. 对u的每个邻居v，更新$dis$，$dis[v]=min(dis[v],dis[u]+w[u,v])$
    3. 若进行了有效的更新，把v压入r中

  • 最后检查每个$dis[i]$，若为INF则说明该点没跑过，返回$-1$；否则返回$dis[i]$

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    void dijkstra(int s) {
	memset(d, 63, sizeof(d));//初始化成一个很大的值
	d[s] = 0;               //初始化起点dis[s]=0
	r.push({ s,0 });       //先推一个进队列
	while (!r.empty()) {
		int u = r.top().dex;
		r.pop();
		if (!vis[u]) {
			vis[u] = true;
			for (auto it : e[u]) {
				int v = it.v;
				ll dis = it.dis;
				if (d[v] > d[u] + dis) {
					d[v] = d[u] + dis;    //更新
					r.push({v , d[v]});  //有效更新，把点推入队列里
				}
			}
		}
	}
}

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

  struct road {
  	int dex;
  	ll dis;
  	friend bool operator < (road a, road b){ return a.dis > b.dis; }//重载<,按val从小到大
  };
  struct edge {
  	int v;//节点u->v
  	ll dis;
  };
  priority_queue <road > r;//重载了基层
  ll d[100010];
  bool vis[100010];
  vector<edge> e[200010];//就是vector实现邻接矩阵orz
  edge tem;
  void dijkstra(int s) {
  	memset(d, 63, sizeof(d));//初始化成一个很大的值1061109567
  	d[s] = 0;
  	r.push({ s,0 });
  	while (!r.empty()) {
  		int u = r.top().dex;
  		r.pop();
  		if (!vis[u]) {
  			vis[u] = true;
  			for (auto it : e[u]) {
  				int v = it.v;
  				ll dis = it.dis;
  				if (d[v] > d[u] + dis) {
  					d[v] = d[u] + dis;//更新
  					r.push({v , d[v]});
  				}
  			}
  		}
  	}
  }
  void solve() {
  	int i, j;
  	int n,m, s;
  	siii(n, m, s);
  	for (i = 0; i < m; i++) {
  		int a, b;
  		ll c;
  		sii(a, b); scanf("%lld", &c);
  		e[a].push_back({b , c});//直接{}就不需要中间量了
  	}
  	dijkstra(s);
  	for (i = 1; i <= n; i++) {
  		if (i == s)
  			printf("%d\n", 0);
  		else {
  			if (vis[i])
  				printf("%lld\n", d[i]);
  			else
  				printf("%d\n", -1);
  		}
  	}
  }
  int main() {
  	int t;
  	/*si(t);
  	while (t--)*/
  	solve();
  	return 0;
  }

Q. 建设道路

题意： n个节点，每个节点都值$A_i$，要求在n个节点中建n-1条边使图连通，建i **到j**的边的代价为$i-j\times D+A_i+A_j$。

求建边的最小代价总和。

最小生成树，分治

因为是完全图，直接建图跑最小生成树会超时/超内存。为了减少边数，可以采用分治的方法

  • 将所有点分成两部分，只考虑跨两部分的建边。设左半部分为i,右半部分为j，则i和j建边的代价即为$(A_i+i*D)+(A_j- j *D)$

  • 对与左半部分，找出$min(A_i+i*D)$对应的i，右半部分找出j，将i和j与对面的点建边即可。

    1
2
3
4
5
6
7
8
9
10

    void add(int tar, int l, int mid, int r, int type) {
	if (type) {//将b的mid->r部分连到a的A(找到的最小的那个点)
		for (int i = r; i > mid; i--)
			e.insert({ tar, i, a[tar] + b[i] });
	}
	else {//将a的l->mid部分连到b的B(找到的最小的那个点)
		for (int i = l; i <= mid; i++)
			e.insert({ i,tar,a[i] + b[tar] });
	}
}

  • 每部分是一半一半处理的，即对于l和r，左半部分找l到mid，右半部分找mid到r。继续上述操作，r更新为mid或l更新为mid+1(要跑两次)

    1
2
3
4
5
6
7
8
9
10
11

    void fz(int l, int r) {//高贵的分治
	if (l != r) {
		int mid = (l + r) / 2;//找中点
		int A = findm(a, l, mid, 1);//找a部分在l到mid区间的最小
		int B = findm(b, mid, r, 0);//找b部分在mid到r区间的最小
		add(A, l, mid, r, 1);//加边
		add(B, l, mid, r, 0);
		fz(l, mid);//r更新为mid再跑一遍
		fz(mid + 1, r);//l更新为mid+1再跑一边
	}
}

  • 建图完成后跑一边Kruskal得到最小生成树

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

int n, d, m;
struct road {//对于点
	int u, v;
	ll w;
	bool friend operator < (road a, road b) { return a.w < b.w; }
};
bool cmp(road a, road b) { return a.w < b.w; }
int fa[200010];
ll a[200010], b[200010];
inline signed gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
ll cost(ll a, int ai, ll b, int bi) { return (ll)jd(ai - bi) * (ll)d + (ll)a + (ll)b; }//计算权重
ll an;
multiset<road>e;
int findm(ll* c, int l, int r, int type) {//找最小的
	int ai;
	if (type) {//l -> mid
		ai = l;
		for (int i = l; i <= r; i++)
			if (c[ai] > c[i])
				ai = i;
	}
	else {//mid -> r
		ai = r;
		for (int i = r; i > l; i--)
			if (c[ai] > c[i])
				ai = i;
	}
	return ai;
}
void add(int tar, int l, int mid, int r, int type) {
	if (type) {//将b的mid->r部分连到a的A
		for (int i = r; i > mid; i--)
			e.insert({ tar, i, a[tar] + b[i] });
	}
	else {
		for (int i = l; i <= mid; i++)
			e.insert({ i,tar,a[i] + b[tar] });
	}
}
void holyshit(int l, int r) {//高贵的分治
	if (l != r) {
		int mid = (l + r) / 2;
		int A = findm(a, l, mid, 1);
		int B = findm(b, mid, r, 0);
		add(A, l, mid, r, 1);
		add(B, l, mid, r, 0);
		holyshit(l, mid);
		holyshit(mid + 1, r);
	}
}
void solve() {
	sii(n, d);
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
		int tem; si(tem);
		a[i] = (ll)tem - (ll)d * (ll)i;
		b[i] = (ll)tem + (ll)d * (ll)i;
	}
	holyshit(1, n);
	for (auto it : e) {
		int x, y;
		if ((x = gf(it.u)) != (y = gf(it.v))) {
			fa[x] = y;
			an += it.w;
		}
	}
	printf("%lld", an);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

R. 建设道路2

题意：给定一个有n个节点的有向图，起点为r，m条边(u->v权值w)，求每个r到每个点之和的最小值。

就是求有向图的最小生成树，即最小树形图。

朱刘算法（Edmods算法）

算法流程：

  • 对每个点，选择它的入边中权值最小的那个边(根节点除外，根没入边)

    1
2
3
4
5
6
7
8

    for (int i = 0; i < m; i++) {
			int a, b;
			a = e[i].v;
			if ( ined[a] > (b = e[i].w)) {
				ined[a] = b;//a点入边的权值
				pre[a] = e[i].u;//a的入边的点
			}
		}

  • 若出现环，将环缩点后更新其他点到环的距离。关于更新距离：

    1. 若这个边在环内则删去这条边
    2. 若该边的终点在环上，其权值更新为：原来的权值-该点在环里对应入边的权值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for (int i = 1; i <= n; i++) {
			if (i != root) {
				an += ined[i];//更新一下答案
				for (tem = i; tem != root && vis[tem] != i && !id[tem]; tem = pre[tem])
				    vis[tem] = i;     //不为根 + 未被访问过（防止一直跑环） + 未被缩环
					                 //赋值i，区分操作区间
				if (vis[tem] == i && tem != root) {//由于每个点都有入边，若满足该式，则必成环
					cut++;
					int flag = 1;
					for (int j = tem; flag || j != tem; j = pre[j]) {//把这个环的id统一一下，缩环
						flag = 0;
						id[j] = cut;
					}
				}
			}
		}

该算法还可以用Tarjan优化 最小树形图 - OI Wiki (oi-wiki.org)

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d%d",&a,&b)
#define siii(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define fl float
#define ll long long int
#define ull unsigned long long int
using namespace std;
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
int jd(int a) { return a < 0 ? (a * -1) : a; }
int n, m, r;
struct road {
	int u, v;
	ll w;
	//bool friend operator < (road a, road b) { return a.w < b.w; }
};
int fa[10010];
inline signed gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
ll an;
vector<road> e;
int flag, tem, root, cut;
int vis[110];
int id[110];//记录缩环标号
int pre[110];//pre[i]记录是i点的入边
ll ined[110];//入边边权(最小)
void START() {//初始化
	cut = 0;
	memset(ined, 88, sizeof(ined));
	memset(vis, 0, sizeof(vis));
	memset(id, 0, sizeof(id));
}
bool jud() {
	for (int i = 1; i <= n; i++) {
		if (ined[i] > 1e9 && i != root)//没有入边且不为根节点
			return true;
	}
	return false;
}
void Edmonds() {
	while (1) {
		START();
		for (int i = 0; i < m; i++) {
			int a, b;
			a = e[i].v;
			if ( ined[a] > (b = e[i].w)) {
				ined[a] = b;
				pre[a] = e[i].u;
			}
		}
		/*for (auto it : e) {
			if (ined[it.v] > it.w) {//每个点选它的入边里权值小的
				ined[it.v] = it.w;
				pre[it.v] = it.u;
			}
		}*/
		if (jud()) {
			an = -1;
			return;
		}
		for (int i = 1; i <= n; i++) {
			if (i != root) {
				an += ined[i];
				for (tem = i; tem != root && vis[tem] != i && !id[tem]; tem = pre[tem])//不为根 + 未被访问过（防止一直跑环） + 未被缩环
					vis[tem] = i;//赋值i，区分操作区间
				if (vis[tem] == i && tem != root) {//每个点都有入边，若满足该式，则必成环
					cut++;
					int flag = 1;
					for (int j = tem; flag || j != tem; j = pre[j]) {//把这个环的id统一一下，缩环
						flag = 0;
						id[j] = cut;
					}
				}
			}
		}
		if (!cut) return;//没缩环就能结束了
		for (int i = 1; i <= n; i++)
			if (!id[i])
				id[i] = ++cut;//给没缩环的点标号
		root = id[root];//更新根的标号
		/*for (int i = 0; i < m; i++) {
			int tem = e[i].v;
			e[i].u = id[e[i].u];
			e[i].v = id[tem];
			if (e[i].u != e[i].v) e[i].w -= ined[tem];
		}*/
		int sum = 0 ;
		for (int i = 0; i < m; i++)
			if (id[e[i].u] != id[e[i].v]) //如果边的两点标号不一样,覆盖、更新
				e[sum++] = { id[e[i].u],id[e[i].v],e[i].w - ined[e[i].v] };
		n = cut;
		m = sum;
	}
}
void solve() {
	siii(n, m, r);
	root = r;
	int sum = 0;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		siii(a, b, c);
		if (b != r && a != b) {//指向根的不要，自环不要
			e.push_back({ a,b,(ll)c });
			sum++;
		}
	}
	m = sum;//更新边数
	Edmonds();
	printf("%lld", an);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

T. 我彻底理解了V圈！

题意：给定一个有向无环图，求最小路径覆盖

由于每个点最多只有一个入边一个出边，显然最小路径的数量为点数-边数。点数是固定的，所以我们求边数最大即可。

最小路径覆盖

对一个节点a，当我们想将a指向b，但b已经被其他点c指向的时候，可以判断一下是否能做到断开c->b让c连其他点，然后连a->b，这样边数就能加一。

1
2
3
4
5
6
7
8
9
10
11

bool jud(int u) {//判断能不能断开重连一条
	for (auto v : e[u])
		if (!vis[v]) {
			vis[v] = 1;                   //two记录点的入边的那个点
			if (!two[v] || jud(two[v])) {//这条点没用过或者对于v可以可以断一条（重连另一条）
				two[v] = u;
				return true;//边数加一
			}
		}
	return false;
}

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

vector<int>e[12010];
vector<int>e2[12010];
set<int>pp;
int vis[12010];
int two[12010];// two[i] -> i
int p_cut;
bool jud(int u) {
	for (auto v : e[u])
		if (!vis[v]) {
			vis[v] = 1;
			if (!two[v] || jud(two[v])) {//这条点没用过或者可以断一条（重连另一条）
				two[v] = u;
				return true;
			}
		}
	return false;
}
void twomax(int u) {
	if (vis[u])
		return;
	vis[u] = 1;
	for (auto v : e[u]) {
		if (!vis[v]) {
			vis[v] = 1;
			if (!two[v]) {
				two[v] = u;//v和u连
				p_cut++;
				return;
			}
			else {
				if (jud(two[v])) {//找v所连边后有没有合理的边了
					two[v] = u;
					p_cut++;
					return;
				}
			}
		}
	}
}
void solve() {
	int n, m;
	sii(n, m);
	for (int i = 0; i < m; i++) {
		int a, b; sii(a, b);
		e[a].push_back(b);
	}
	for (int i = 1; i <= n; i++) {
		if (!e[i].empty()) {
			memset(vis, 0, sizeof(int)*(n+1));
			twomax(i);
		}
	}
	printf("%d", n - p_cut);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

EX. 补图联通块数量

https://codeforces.com/gym/388925/problem/H 无向完全图，给你一些权值为1的边，其余边为0，求最小生成树

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

#include <bits/stdc++.h>
template<typename T>
inline void read(T& x) { x = 0; char c = getchar(); while (!isdigit(c))c = getchar(); while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } }
#define si(a) read(a)
#define sii(a,b) read(a),read(b)
#define siii(a,b,c) read(a),read(b),read(c)
#define fl float
#define ll long long int
#define ull unsigned long long int
using namespace std;
const ll MOD = 1e9 + 7;
const int N = 2e5 + 10;
//int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
ll gcd(ll a, ll b) { return a == 0 ? b : gcd(b % a, a); }
int n, d, m;
int fa[N];
inline signed gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
//inline signed gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
vector<int>e[N];
vector<int>now;//
map<int, int>mp;
int sz[N];
int ans = 0;
void solve() {
	sii(n, m);
	for (int i = 1; i <= m; i++) {
		int u, v; sii(u, v);
		e[max(u, v)].push_back(min(u, v));
	}
	for (int i = 1; i <= n; i++)fa[i] = i, sz[i] = 1;
	for (int i = 1; i <= n; i++) {
		mp.clear();
		for (auto it : e[i])mp[gf(it)]++;
		int x, y;
		for (int j = 0; j < now.size(); j++) {//遍历所有联通块
			x = gf(i),y = gf(now[j]);
			if (x != y)
				if (mp[y] < sz[y])//说明点与该连通块直接有0权边
					sz[y] += sz[x], fa[x] = y;
		}
		if (fa[i] == i)//更新连通块
			now.push_back(i);
	}
	for (int i = 1; i <= n; i++)
		if (fa[i] == i)ans++;
	printf("%d", ans-1);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}
/*

*/

EX2. 拓扑排序

Animals are waiting in a line, in a quarantine zone, before they can enter a hunting-free area, where they will find an easier life.

When entering the quarantine zone, animals have to check in with a guard. The guard writes down the animal species, and then the animal is allowed to join the end of the line, in the last position. At the other end of the line, animals have to check out: when the animal in the first position in the line is finally allowed to enter the hunting-free area, another guard writes down the animal species. Thus, each guard maintains a list of animal species, written down in the chronological order in which the animals have checked in or out. A total of NN animals, representing SS species, have checked in (and, therefore, checked out).

However, animals may enter the waiting line and leave it in different orders. Indeed, some animal species are friends with each other, and thus two animals from such species, if they occupy adjacent places in the line may accept to switch their places.

You have a list of those pairs of animal species that may accept to switch their places when being in adjacent positions in the line: this list contains L pairs. You were handed out the check-in list maintained by the first guard. Depending on which animals decided to switch places, several check-out lists might be possible. Among all those possible lists, which one comes first in alphabetical order?

给你S个物种，L个朋友关系，相邻且是朋友关系的两个可以互换位置，对N个动物排序使其字典序最小

不能换位置的即为约束关系，建有向边，同时每个动物只要考虑与它前面动物的约束关系

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
76
77
78
79
80
81
82
83
84
85

#include <bits/stdc++.h>
template<typename T>
inline void read(T& x) { x = 0; char c = getchar(); while (!isdigit(c))c = getchar(); while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } }
#define si(a) read(a)
#define sii(a,b) read(a),read(b)
#define siii(a,b,c) read(a),read(b),read(c)
#define fl double
#define ll long long int
#define ull unsigned long long int
#define T ll
using namespace std;
const ll MOD = 1e9 + 7;
//const int N = 2e5 + 10;//                       这个容易改的啊！！！！！！！
//int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
ll gcd(ll a, ll b) { return a == 0 ? b : gcd(b % a, a); }
int n, m;
int S, L, N;
vector<string>species(1);//这个1不能少
map<string, int> mp;
int Friend[210][210];//朋友关系
int last[210];//同种物种间也有约束，所以不同物种的只用考虑它前面的
vector<int>e[200010];//拓扑建图，有约束条件的建有向边
int du[200010];//入度
int Line[200010];//初始的排队序列
int ans[200010];
struct ani {
	int sp, dex;//物种、在Line里的下标
	friend bool operator < (ani a, ani b) {
		if (a.sp == b.sp)return a.dex > b.dex;
		return a.sp > b.sp;
	}//重载<,按sp从小到大 or dex
};
priority_queue<ani> S_tp;
void tuopu() {
	for (int i = 1; i <= N; i++)if (!du[i])S_tp.push({ Line[i],i });
	int cnt = 0;
	while (!S_tp.empty()) {
		ani tmp = S_tp.top();
		S_tp.pop();
		ans[++cnt] = tmp.dex;
		for (auto it : e[tmp.dex])
			if (--du[it] == 0)S_tp.push({ Line[it],it });
	}
}
void solve() {

	siii(S, L, N);
	for (int i = 1; i <= S; i++) {
		string tmp; cin >> tmp;//string 不能直接用 scanf
		species.push_back(tmp);
	}
	sort(species.begin(), species.end());//这里要用begin()和end()
	int tmp = 0;
	for (auto it : species) mp[it] = tmp++;
	for (int i = 1; i <= L; i++) {
		string x, y; cin >> x >> y;
		Friend[mp[x]][mp[y]] = 1;
		Friend[mp[y]][mp[x]] = 1;
	}
	for (int i = 1; i <= N; i++) {
		string tmp; cin >> tmp;
		int id = mp[tmp];
		Line[i] = id;
		for (int j = 1; j <= S; j++) {
			if (Friend[id][j] || !last[j])
				continue;
			e[last[j]].push_back(i);
			du[i]++;//入度加一
		}
		last[id] = i;
	}
	tuopu();
	for (int i = 1; i <= N; i++)cout << species[Line[ans[i]]] << ' ';
}
int main() {
	int t;
	t = 1;
	//si(t);
	while (t--)
		solve();
	return 0;
}
/*

*/
Study, ACM
Graph ACM
This post is licensed under CC BY 4.0 by the author.