原题链接
思路： 先利用已给的边求出每个政府树的顶点数（深度搜索） 选出顶点数最多的政府树，将剩余的与政府点不连通的点加入该树 此时所有的点被分为k组，将每组中的点全部连同，可以得到最大总边数，减去已有边就是答案。
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <queue>#include <vector> #include <set>#define INF 100000000using namespace std; int n, m, k; //总点数，已有边数，政府数（树数） int c[1050]; //政府所在点 vector<int> g[1050]; //g[i]中有所有与i直接相连的点int v, vmax, res;bool vis[1050];void dfs(int s){ int i; v++; vis[s] = true; //s点已经在某个政府树中 for(i = 0; i < g[s].size(); i++){ int p = g[s][i]; if(!vis[p]){ vis[p] = true; dfs(p); } }}int main(){ int i, j; scanf("%d %d %d", &n, &m, &k); for(i = 0; i < k; i++){ scanf("%d", &c[i]); } for(i = 1; i <= m; i++){ int b, c; scanf("%d %d", &b, &c); g[b].push_back(c); g[c].push_back(b); } for(i = 0; i < k; i++){ v = 0; //与该政府顶点同树的点 dfs(c[i]); res += v*(v-1)/2; //先将每个政府顶点所在树上的点全部相连 n -= v; //剩余与任何政府顶点不同树的点减少v vmax = max(vmax, v); //找出所有政府顶点所在树中顶点数最多的树 } res += n*(n-1)/2; //将剩余所有无法到达政府顶点的点相互连接 res += n*vmax; //将这些点与已有的点数最多的树相连 res -= m; //减去已有的边 PRintf("%d/n",res); return 0;}新闻热点
疑难解答
