http://codeforces.com/contest/745/problem/C

把他们并查集后,

其他没有连去government的点,全部放去同一个并查集,然后选择一个节点数最多的government集合,连接过去即可。

至于有多少条边增加,可以暴力判断。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e4 + ;
int fa[maxn];
int tofind(int x) {
if (fa[x] == x) return x;
else return fa[x] = tofind(fa[x]);
}
void tomerge(int x, int y) {
x = tofind(x);
y = tofind(y);
if (x != y) fa[y] = x;
}
int tohash[maxn];
bool e[maxn][maxn];
vector<int>gg[maxn];
int cc[maxn];
int id[maxn];
bool vis[maxn];
bool has[maxn];
void work() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= maxn - ; ++i) fa[i] = i;
for (int i = ; i <= k; ++i) {
int x;
scanf("%d", &x);
tohash[x] = ;
cc[i] = x;
}
for (int i = ; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
e[u][v] = e[v][u] = ;
tomerge(u, v);
}
for (int i = ; i <= n; ++i) {
gg[tofind(i)].push_back(i);
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 0; j < gg[tofind(i)].size(); ++j) {
// printf("%d ", gg[tofind(i)][j]);
// }
// printf("\n");
//
// }
int lenid = ;
for (int i = ; i <= n; ++i) {
if (vis[tofind(i)]) continue;
vis[tofind(i)] = true;
// cout << "ff" << endl;
bool flag = false;
for (int j = ; j < gg[tofind(i)].size(); ++j) {
if (tohash[gg[tofind(i)][j]]) {
flag = true;
has[tofind(i)] = true;
break;
}
}
if (!flag) {
id[++lenid] = tofind(i);
}
}
int togo = n + ;
for (int i = ; i <= lenid; ++i) {
tomerge(togo, id[i]);
}
for (int i = ; i <= n; ++i) {
if (has[tofind(i)]) continue;
// cout << "ff" << endl;
assert(tofind(i) == togo);
gg[tofind(i)].push_back(i);
}
int ans = ;
int mx = -inf;
memset(vis, , sizeof vis);
for (int i = ; i <= n; ++i) {
if (!has[tofind(i)]) continue;
// cout << "ff" << endl;
if (vis[tofind(i)]) continue;
vis[tofind(i)] = true;
int tt = gg[tofind(i)].size();
mx = max(mx, tt);
for (int j = ; j < gg[tofind(i)].size(); ++j) {
for (int k = j + ; k < gg[tofind(i)].size(); ++k) {
int u = gg[tofind(i)][j];
int v = gg[tofind(i)][k];
if (!e[u][v]) {
ans++;
// cout << u << " " << v << endl;
}
}
}
}
if (lenid != ) {
// cout << ans << endl;
// cout << "ff" << endl;
for (int i = ; i < gg[togo].size(); ++i) {
for (int j = i + ; j < gg[togo].size(); ++j) {
int u = gg[togo][i];
int v = gg[togo][j];
if (!e[u][v]) ans++;
}
}
}
// cout << ans << endl;
// cout << gg[id[1]].size() << endl;
ans += mx * gg[togo].size();
cout << ans << endl;
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}

最新文章

  1. &lt;转&gt;SQL Server返回最后一个标识值的三个函数:IDENT_CURRENT、@@IDENTITY、SCOPE_IDENTITY
  2. contiki-rime-单跳单播
  3. Java-接口和抽象类区别
  4. delphi 开发者 linux 实务(转)
  5. 两个Canvas小游戏
  6. linux之samba与linux权限
  7. html中input文本框,初始里边有文字提示,当点击时,文字消失,怎么设置?
  8. my ambition
  9. 可配置多功能门 SN74LVC1G57, 1G58, 1G97, 1G98, 1G99
  10. Linux下修改用户home目录
  11. HIT 1867 经理的烦恼
  12. Web---Cookie技术(显示用户上次登录的时间、显示用户最近浏览的若干个图片(按比例缩放))
  13. MySQL Error Handling in Stored Procedures---转载
  14. 利用WSGI来部署你的网站
  15. (转) int argc, char* argv[] 的用法
  16. Python: how to public a model
  17. net.sf.json 迄今 时刻 格式 办法
  18. 注意Vietnamese_CI_AS排序规则下的特殊字符大小敏感问题
  19. Switch控件详解
  20. 【原创】大叔问题定位分享(14)Kylin频繁OOM问题

热门文章

  1. 读书笔记-HBase in Action-第三部分应用-(2)GIS系统
  2. ym——优化你的Java代码(新)
  3. Android之——监听手机开机事件
  4. iOS 配置支付宝
  5. 【iOS系列】-autorelease的作用
  6. 从头认识java-15.1 填充容器(3)-填充Map
  7. IIS7添加虚拟目录映射另一台服务器的共享文件夹
  8. 什么是 jQuery EasyUI
  9. Delphi XE10调用WebService服务获取图片验证码
  10. YTU 2440: C++习题 复数类--重载运算符+,-,*,/