最小生成树

其实这道题完全是一道水题,像我这样随便乱搞都可以过....
刚看到这道题,我就意识到他绝对与最小生成树有关.
于是直接上了模板,万万没想到,他过了.....

时间复杂度 $O(nlogn)$

C++ 代码

//相信奇迹的人,本身就和奇迹一样了不起.
#include<bits/stdc++.h>
#define N 20
using namespace std;
struct node{
    int from,to,dis;
}e[N*N];
int n,m,v[N],in[N];//in数组记录有几条边与该点有关,方便判联通
int fa[N],tot,cnt;
bool rule(const node &a,const node &b)//按边权从小到大排序
{
    return a.dis<b.dis;
}
int find(int x)//路径压缩
{
    if(fa[x]==x)
        return fa[x];
    return fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        scanf("%d",&v[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].dis);
        e[i].from++,e[i].to++;
        in[e[i].from]++,in[e[i].to]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i]&&v[i]){//如果没有一条边与这个点有关,且这个点的v[i]不为0,表明这个点永远不可能与其他点能量一 //样,直接输出Impossible
            puts("Impossible");
            return 0;
        }
    sort(e+1,e+1+m,rule);
    for(int i=1;i<=m;i++){//克鲁斯卡尔算法求最小生成树
        if(tot==n-1)
            break;
        int u=e[i].from,v=e[i].to;
        if(find(u)!=find(v)){
            fa[find(v)]=find(u);
            cnt+=e[i].dis;
            tot++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}