天空之城

思路

• 因为走重复的路不被计算，所以很容易看出这是求最小生成树
• 注意用long long

代码

// Problem: 天空之城
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9986/J
// Memory Limit: 1048576 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m,fa[N],depth[N];
struct edge{
    int u,v;
    ll w;
}e[N];

bool cmp(edge x,edge y){
    return x.w<y.w;
}

void init(int n){
    for(int i=1;i<=n;i++) 
        fa[i]=i,depth[i]=1;
}
//查询树的根
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
//合并a和b所属的集合   
void unite(int a,int b){
    a=find(a),b=find(b);
    if(depth[a]==depth[b]){
        depth[a]=depth[a]+1;
        fa[b]=a;
    }
    else{
        if(depth[a]<depth[b]) fa[a]=b;
        else fa[b]=a;
    }
}
//判断a和b是否属于同一个集合
bool same(int a,int b){
    return find(a)==find(b);
}

ll Kruskal(){
    ll res=0;
    int count=0;
    for(int i=0;i<m;i++){
        if(!same(e[i].u,e[i].v)){
            unite(e[i].u,e[i].v);
            res+=e[i].w;
            count++;
        }
        if(count==n-1) return res;
    }
    return -1;
}


void solve(){
    init(n);
    map<string,int> id;
    int t=0;
    string op;cin>>op;id[op]=++t;
    rep(i,0,m-1) {
        string a,b;ll d;
        cin>>a>>b>>d;
        if(!id.count(a)) id[a]=++t;
        if(!id.count(b)) id[b]=++t;
        e[i]={id[a],id[b],d};
    }
    sort(e,e+m,cmp);
    ll k=Kruskal();
    if(k==-1) cout<<"No!\n";
    else cout<<k<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    while(cin>>n>>m) solve();
    return 0;
}