CodeForces744AHongcowBuildsANation(并查集+容斥)

题意&＃xff1a;

        给出一个无向图&＃xff0c;有N个点&＃xff0c;M个边和K个根节点。问在保证根节点间无通路时&＃xff0c;最多加多少条边。

思路&＃xff1a;

        利用并查集计算出每个根对应的集合中点的个数后&＃xff0c;显然我们有三种点集&＃xff1a;

                1.点数最多的有根点集

                2.其他有根点集

                3.无根点集

        满足以上条件加边后的状态为

                1.点数最多的有根点集构成完全图

                2.其他有根点集构成完全图

        就剩无根点集了&＃xff0c;显然无根点集也要构成完全图&＃xff0c;而且要与且仅能与一个有根点集相连

        那么要想得到最多的边&＃xff0c;就要把无根点集与点数最多的有根点集相连

        利用一点容斥的思想可以得到    要加边数 &＃61; 所有点集完全图的边数 &＃43; 无根点集的点数 * 点数最多的有根点集的点数 - 现有的边数 M

        或者我们可以把无根点集直接加入点数最多的有根点集&＃xff0c;那么 要加边数 &＃61; 所有点集完全图的边数 - 现有的边数 M

代码&＃xff1a;

#include using namespace std;
const int MAXN&＃61;1010;
int num[MAXN],F[MAXN];
int find(int t)
{if(F[t]&＃61;&＃61;t) return t;return F[t]&＃61;find(F[t]);
}
void bing(int a,int b)
{int t1&＃61;find(a);int t2&＃61;find(b);if(t1!&＃61;t2) F[t1]&＃61;t2;
}
int main()
{int n,m,k,t1,t2;int cap[MAXN];while(cin>>n>>m>>k){memset(num,0,sizeof(num));for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)F[i]&＃61;i;for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;)scanf("%d",&cap[i]);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d",&t1,&t2);bing(t1,t2);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)num[find(i)]&＃43;&＃43;;int maxn&＃61;0,lef&＃61;n;int ans&＃61;0;for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){num[cap[i]]&＃61;num[find(cap[i])];maxn&＃61;max(maxn,num[cap[i]]);lef-&＃61;num[cap[i]];ans&＃43;&＃61;(num[cap[i]]-1)*(num[cap[i]])/2;}ans&＃43;&＃61;(lef&＃43;maxn)*(lef&＃43;maxn-1)/2;ans-&＃61;maxn*(maxn-1)/2&＃43;m;cout<}


For the first sample test, the graph looks like this:

Vertices 1 and 3 are special. The optimal solution is to connect vertex 4 to vertices 1 and 2. This adds a total of 2 edges. We cannot add any more edges, since vertices 1 and 3 cannot have any path between them.

For the second sample test, the graph looks like this:

We cannot add any more edges to this graph. Note that we are not allowed to add self-loops, and the graph must be simple.