这个题就是畅通工程的翻版好吗,一样可以用Prim和Kus算法来解。要注意的就是输入输出,cin、cout可能更好用

一以前的代码写的太low,更新了一下代码,prim改为优先队列优化,kruskal删除了一个莫名Wa的父节点交换,还是太年轻啊

题目:飞机票直达(F - Jungle Roads

下面是代码:

Prim算法:

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int maxn=28;
struct edge{
    edge(int v, int c){to=v,cost=c;}
    edge(){}
    int to, cost;

    bool operator<(const edge &cmp)const{
        return cost>cmp.cost;
    }
};

char cu, cv;
int n, ku, kv;
int vis[maxn];

priority_queue<edge> que;
vector<edge> E[maxn];

int Prim(){
    int ans=0;
    vis[0]=1;
    for(int i=0;i<E[0].size();i++){
        que.push(E[0][i]);
    }
    while(!que.empty()){
        edge e=que.top();
        que.pop();
        if(vis[e.to])continue;
        vis[e.to]=1;
        ans+=e.cost;
        for(int i=0;i<E[e.to].size();i++){
            que.push(E[e.to][i]);
        }
    }
    return ans;
}

int main(){
    while(~scanf("%d", &n)&&n){
        memset(vis, 0, sizeof(vis));
        for(int i=0;i<maxn;i++)E[i].clear();
        while(!que.empty())que.pop();
        for(int i=0;i<n-1;i++){
            scanf("%s%d", &cu, &ku);
            for(int j=0;j<ku;j++){
                scanf("%s%d", &cv, &kv);
                E[cu-'A'].push_back(edge(cv-'A', kv));
                E[cv-'A'].push_back(edge(cu-'A', kv));
            }
        }
        printf("%d\n", Prim());
    }
}

Kus算法:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=100;

struct edge{
    int u, v, cost;
    bool operator<(const edge &cmp) const{
        return cost<cmp.cost;
    }
}E[maxn];

int n, ku, kv, cnt;
char cu, cv;
int fa[maxn];

int Find(int x){
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}

int Kruskal(){
    int ans=0;
    for(int i=0;i<cnt;i++){
        int fu=Find(E[i].u);
        int fv=Find(E[i].v);
        if(fu!=fv){
            fa[fu]=fv;
            ans+=E[i].cost;
        }
    }
    return ans;
}

int main()
{
    while(~scanf("%d", &n)&&n){
        cnt=0;
        for(int i=0;i<maxn;i++)fa[i]=i;
        for(int i=0;i<n-1;i++){
            scanf("%s%d", &cu, &ku);
            for(int i=0;i<ku;i++){
                scanf("%s%d", &cv, &kv);
                E[cnt].u=cu-'A';
                E[cnt].v=cv-'A';
                E[cnt].cost=kv;
                cnt++;
            }
        }
        sort(E, E+cnt);
        printf("%d\n", Kruskal());
    }
    return 0;
}