1.Einstin学画画：
题目链接：P1636 Einstein学画画 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1 #include<bits/stdc++.h>
2 using namespace std;
3 int vis[1005];
4 int n, m;
5 int ans;
6 int main()
7 {
8 cin >> n >> m;
9 for (int i = 1; i <= m; i++)
10 {
11 int u, v;
12 cin >> u >> v;
13 vis[u]++;
14 vis[v]++;
15 }
16 for (int i = 1; i <= n; i++)
17 {
18 if (vis[i] % 2 == 1) ans++;
19 }
20 if (ans == 0) cout<< 1;
21 else cout << ans/2;
22 return 0;
23 }
2.合根植物：
题目链接：P8654 [蓝桥杯 2017 国 C] 合根植物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1 #include<bits/stdc++.h>
2 using namespace std;
3 long long fa[1000005];//本题数据较大，需要开long long
4 long long vis[1000005];
5 long long n, m, k;
6 long long ans;
7 int find(long long x)//查询操作
8 {
9 if (fa[x] == x) return x;
10 else
11 {
12 fa[x] = find(fa[x]);
13 return fa[x];
14 }
15 }
16 void merge(long long i, long long j)//合并操作
17 {
18 fa[find(i)] = find(j);
19 }
20 int main()
21 {
22 cin >> n >> m >> k;
23 for (int i = 1; i <= m * n; i++) fa[i] = i;//初始化操作
24 for (int i = 1; i <= k; i++)
25 {
26 int u, v;
27 cin >> u >> v;
28 merge(u, v);
29 }
30 for (int i = 1; i <= m * n; i++) find(i);//菊花图操作
31 for (int i = 1; i <= n * m; i++)
32 {
33 if ( vis[fa[i]] == 1) continue;
34 vis[fa[i]] = 1;
35 ans++;
36 }
37 cout << ans << endl;
38 return 0;
39 }
3.奶酪：
题目链接：
1 #include<bits/stdc++.h>
2 using namespace std;
3 long long fa[1005];//这题数据也很大，记得开long long
4 long long n, h, r, T;
5 long long X[1005], Y[1005], Z[1005],x,y,z;
6 long long ans;
7 int find(long long x)//查询操作
8 {
9 if (fa[x] == x) return x;
10 else
11 {
12 fa[x] = find(fa[x]);
13 return fa[x];
14 }
15 }
16 void merge(long long i, long long j)//合并操作
17 {
18 fa[find(i)] = find(j);
19 }
20 bool dis(long long x1,long long x2,long long y1, long long y2,long long z1 ,long long z2,long long r)//用于判断两球是否相切或相交
21 {
22 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2) <= 4 * r * r;
23 }
24 int main()
25 {
26 cin >> T;
27 for (int i = 1; i <= T; i++)
28 {
29 //题目存在多组数据，每次开始记得初始化
30 memset(X, 0, sizeof(X));
31 memset(Y, 0, sizeof(Y));
32 memset(Z, 0, sizeof(Z));
33 cin >> n >> h >> r;
34 for (int j = 1; j <= n; j++) fa[j] = j;
35 fa[1001] = 1001;//1001代表底部
36 fa[1002] = 1002;//1002代表顶部
37 for (int j = 1; j <= n; j++)
38 {
39 cin >> x >> y >> z;//输入数据
40 X[j] = x, Y[j] = y, Z[j] = z;
41 }
42 for (int j = 1; j <= n; j++)
43 {
44 if (Z[j] <= r) merge(j, 1001);
45 if (Z[j] + r >= h) merge(j, 1002);
46 }
47 for (int j = 1; j <= n; j++)
48 {
49 for (int k = j + 1; k <= n; k++)
50 {
51 if (dis(X[j], X[k], Y[j], Y[k], Z[j], Z[k], r))merge(j, k);//遍历所有点，两圆相连则加入一棵树
52 }
53 }
54 if (find(1001) == find(1002)) cout << "Yes" << endl;
55 else cout << "No" << endl;
56 }
57 return 0;
58 }
4.灾后重建：
题目链接：P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n, m;
4 int u, v, w;
5 int hour[205];
6 int maze[205][205];
7 int main()
8 {
9 cin >> n >> m;
10 for (int i = 0; i < n; i++)scanf("%d", hour + i);
11 for (int i = 0; i < n; i++)
12 {
13 for (int j = 0; j < n; j++)
14 {
15 maze[i][j] = 1e9;//floyd初始化，所有点最短路设置为无限，自己到自己设置为0
16 maze[i][i] = 0;
17 }
18 }
19 for (int i = 0; i < m; i++)
20 {
21
22 scanf("%d%d%d", &u, &v, &w);
23 maze[u][v] = w;//邻接矩阵存图
24 maze[v][u] = w;
25 }
26 int q,mark=0;
27 cin >> q;
28 for (int i = 0; i < q; i++)
29 {
30 scanf("%d%d%d", &u, &v, &w);
31 //mark = 0;//超时的元凶，实际上我们根本不需要重置mark，因为修路时间和询问时的时间都是单调不减的方式排列
32 while (hour[mark] <= w && mark < n)//floyd三重循环
33 {
34 for (int j = 0; j < n; j++)
35 {
36 for (int k = 0; k < n; k++)
37 {
38 if (maze[j][k] > maze[j][mark] + maze[mark][k]) maze[j][k] = maze[j][mark] + maze[mark][k];
39 }
40 }
41 mark++;
42 }
43 if (hour[u] > w || hour[v] > w )cout << -1 << endl;//如果出发地或目的地村庄还未重建完成
44 else
45 {
46 if (maze[u][v] == 1e9) cout << -1 << endl;//若没有路径
47 cout << maze[u][v] << endl;
48 }
49 }
50 return 0;
51 }
5.聪明的猴子：
题目链接：P2504 [HAOI2006]聪明的猴子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n, m, ans;
4 double x[1005], y[1005];
5 int fa[1005];//并查集中的数组
6 int d[505];
7 struct node
8 {
9 int x, y;
10 double d;
11 }e[1000005];
12 bool cmp(node a, node b)
13 {
14 return a.d < b.d;//结构体排序
15 }
16 int find(int x)//并查集查询
17 {
18 if (fa[x] == x) return x;
19 else
20 {
21 fa[x] = find(fa[x]);
22 return fa[x];
23 }
24 }
25 void merge(int i, int j)//并查集合并
26 {
27 fa[find(i)] = find(j);
28 }
29 int main()
30 {
31 cin >> n;
32 for (int i = 1; i <= n; i++) cin >> d[i];
33 cin >> m;
34 for (int i = 1; i <= m; i++)cin >> x[i] >> y[i];
35 int cnt = 0;
36 for (int i = 1; i <= m; i++)//计算两树距离
37 {
38 for (int j = i+1; j <= m; j++)
39 {
40 cnt++;
41 e[cnt].x = i;
42 e[cnt].y = j;
43 e[cnt].d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
44 }
45 }
46 sort(e + 1, e + 1 + cnt, cmp);//从小到大排序
47 for (int i = 1; i <= m; i++) fa[i] = i;//并查集初始化
48 double M = 0;//存储最大值的变量
49 for (int i = 1; i <= cnt; i++)
50 {
51 if (find(e[i].x) != find(e[i].y))//若二者的根节点不同
52 {
53 merge(e[i].x, e[i].y);
54 M = max(M, e[i].d);
55 }
56 }
57 for (int i = 1; i <= n; i++)
58 {
59 if (d[i] >= M)ans++;
60 }
61 cout << ans;
62 return 0;
63 }
标签：week10,图论,int,++,long,fa,ACM,maze,find From： https://www.cnblogs.com/Zac-saodiseng/p/17038452.html