首页 > 代码库 > CodeForces - 744A Hongcow Builds A Nation

CodeForces - 744A Hongcow Builds A Nation

2024-09-03 23:24:07   224人阅读

http://codeforces.com/problemset/problem/744/A

这是一道考察连通块的题（做之前， 连通块是什么都不清楚） Note:点的集合 任意两点都有可达的路径

可以用并查集做 在一个政府管辖下的点 作为一个集合 根节点就是这个政府

再者 贪心 ：

要求做多可以添加的边数 做多一个集合 n个点 使它构成完全图 得到的边数为n*(n-1) / 2

那么最终表达式可以为n[1]*(n[1]-1) / 2 + n[2]*(n[2]-1) / 2 +....+ n[k]*(n[k]-1) / 2

　　　　　　　　　　= 1/2 ( (n[1]^2 + n[2]^2 + ... n[k] ^2 ) - (n[1] + n[2] + ... n[k]) );

因为 n[1] + n[2] + ... n[k] 为定值 那么使n[1]^2 + n[2]^2 + ... n[k] ^2 最大 就让最大的值尽量大 结果最大

那么就去计算还未连入政府的点 将它（和相连的点）加入政府的"辖区" --->>unnite

但是一定要注意 计数的方式和时机 不能读到一个不是政府的点就nim++ 要经过处理 把所有的点的根节点都确定 求出来 然后在计数（不要忘记是连通 而不是相连）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <vector>
 5 #include <map>
 6 #include <algorithm>
 7 
 8 #define MAXN 1007
 9 
10 using namespace std;
11 
12 
13 int n, m, k;
14 int g[MAXN], par[MAXN];
15 long long ans = 0;
16 int find(int x)
17 {
18     if (x == par[x]) return x;
19     else return par[x] = find(par[x]);
20 }
21 struct Gov
22 {
23     int x;
24     long long num;
25     bool operator < (Gov a) const
26     {
27         return num > a.num;
28     }
29 };
30 
31 
32 vector<Gov> v;
33 map<int, int> mym;
34 map<int, int> :: iterator it;
35 int main()
36 {
37     freopen("in.txt", "r", stdin);
38     scanf("%d%d%d", &n, &m, &k);
39     fill(g, g+n, 0);
40     for (int i = 1; i <= n; i++) par[i] = i;
41     for (int i = 0; i < k; i++)
42     {
43         int x;
44         scanf("%d", &x);
45         mym[x] = 1;
46         g[x] = x;
47     }
48     for (int i = 0 ;i < m; i++)
49     {
50         int x, y, px, py;
51         scanf("%d%d", &x, &y);
52         px = find(x), py = find(y);
53         if (g[px] && !g[py]) par[py] = px;//px是政府 而py不是政府
54         else if (g[py] && !g[px]) par[px] = py;
55         else if (!g[py] && !g[px]) par[px] = py;//随意连
56     }
57     for (int i = 1; i <= n; i++)
58     {
59         int pi = find(i);
60         //如果根节点被政府管辖 加入管理数
61         if (i != pi && g[pi]) mym[pi] += 1;
62     }
63     //进入vector
64     for (it = mym.begin(); it != mym.end(); it++)
65     {
66         Gov tmp;
67         tmp.x = (*it).first;
68         tmp.num = (*it).second;
69         v.push_back(tmp);
70     }
71     sort(v.begin(), v.end());
72     int tar = v[0].x, num = 0;//最大的政府
73     for (int i = 1; i <= n; i++)
74     {
75         int pi = find(i);
76         if (g[pi] == 0) par[pi] = tar;
77     }
78     for (int i = 1; i <= n; i++)
79     {
80         int pi = find(i);
81         if (g[pi] == tar) num++;
82     }
83     v[0].num = num;
84     for (int i = 0; i < k; i++) ans += (v[i].num-1)*v[i].num / 2;
85     ans -= m;
86     printf("%lld\n", ans);
87 
88 }

 

CodeForces - 744A Hongcow Builds A Nation


联系
我们