题目链接

题意：有一个完全图，然后权值只有0或者1，现在给你权值为1的边，其余权值为0，然后问你这个图的最小生成树的权值是多少。

思路：很显然，我们要尽量多的用权值为0的边。这可怎么考虑呢？

给的是权值为1的边可以形成一张图，这个图必定是原图的一个子图。然后这个子图的补图必定都是权值为0的边。

我们可以考虑原图、补图转化的 思想。考虑补图（权值为0）的连通块个数。然后如果要把这些连通块连在一起的话，需要加权值为1 的边才行。

所以答案 就是 补图的连通块个数 - 1

#include<bits/stdc++.h>
using namespace std;
const int boss=2e5+10;
unordered_map<int,bool> lj[boss];
bitset<boss> b;
int n,m,k,ans[boss];
void dfs(int u)
{
    b[u]=0,ans[k]++;
    for (int i=b._Find_first(); i<b.size(); i=b._Find_next(i))
        if (!lj[u][i])
            dfs(i);
}
int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; i++)
        b[i]=1;
    for (i=1; i<=m; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        lj[u][v]=lj[v][u]=1;
    }
    for (i=1; i<=n; i++)
        if (b[i])
            dfs(i),++k;
    printf("%d\n",k-1);
}

这里还有个神仙代码

#include<bits/stdc++.h>
using namespace std;
const int boss=2e5+10;
unordered_map<int,bool> lj[boss];
bitset<boss> b;
int n,m,k,ans[boss];
void dfs(int u)
{
    b[u]=0,ans[k]++;
    for (int i=b._Find_first(); i<b.size(); i=b._Find_next(i))
        if (!lj[u][i])
            dfs(i);
}
int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; i++)
        b[i]=1;
    for (i=1; i<=m; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        lj[u][v]=lj[v][u]=1;
    }
    for (i=1; i<=n; i++)
        if (b[i])
            dfs(i),++k;
    printf("%d\n",k-1);
}

?