原題鏈接
思路： 先利用已給的邊求出每個政府樹的頂點數（深度搜索） 選出頂點數最多的政府樹，將剩余的與政府點不連通的點加入該樹 此時所有的點被分為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; //減去已有的邊新聞熱點
疑難解答
