樱桃网

题意分析：

本题的意思为，一共有N个节点，两两节点之间都存在一条路径，所有路径的代价都是2。但是因为某些原因，部分路径的代价变成了1，求现在这种情况下这些节点之间的最短路。

思路分析：

1.本题对于我而言，我的第一直觉使用克鲁斯卡尔来解，其时间复杂度为$O(mlogm)$，数据量最大的m为10^5，不会超时。
2.如果使用克鲁斯卡尔，那么就得把所有的边集加入到数组之中，但是题目数据只给出了代价为1的路径，如果想要初始化所有的边集，那么其时间复杂度就会达到$O(n^2)$，进而TLE。Prim算法的时间复杂度为$O(n^2)$，在给定的数据范围下也会TLE。所以综上，使用最小生成树暴力解会超时。

3.既然最小生成树无法实现，那么我们换一种思路分析分析。使用题目给定的代价为1的边产生的连通块的代价一定比使用代价为2的边要小。基于这种思想，我们可以这样做：

3.1 把所有的给定的边的端点连成一个连通块
3.2 假设最后一共有n个点已经形成了连通块，那么这些点连起来的代价为n-1,将剩下的点连进来的代价为（总数 - n） * 2,所以最后的总代价为(n - 1) + (总数 - n) * 2

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6 +10;

int T; 
int n, m;
int f[N];
int num[N], t = 1;

int find(int x)
{
    if(x != f[x])   f[x] = find(f[x]);
    return f[x];
}

int main()
{
    scanf("%d", &T);
    for(int i = 1; i <= T; i ++ )
    {
        t = 1;
        scanf("%d%d", &n, &m);
        for(int j = 1; j <= n; j ++ )
        {
            f[j] = j,num[j] = 1;
        }
        for(int j = 0; j < m; j ++ )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            a = find(a), b = find(b);
            if(a != b)  
            {
                f[b] = a;
                t += num[b];
            }
        }

        cout<<"Case #"<<i<<": "<<((t - 1) + (n - t) * 2)<<endl;
    }
    return 0;
}