Connect the Cities 【HDU - 3371】【Kruskal、变了形的优先队列】

题目链接

就是问你能否通过选取一些边构成一棵树，最小生成树。

这道题的关键不在于此，在于学到了另外一种优先队列的写法：

struct cmp
{
    bool operator ()(Eddge e1, Eddge e2)
    {
        return e1.val>e2.val;
    }
};
priority_queue <Eddge, vector<Eddge>, cmp > Q;

让我的优先队列变得更好看了，并且可以节约大致20～30ms的时间（可以忽略）。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN=505;
int N, M, K, a[maxN], root[maxN];
struct Eddge
{
    int nex, to, val;
    Eddge(int a=0, int b=0, int c=0):nex(a), to(b), val(c) {}
    friend bool operator < (Eddge e1, Eddge e2)
    {
        return e1.val<e2.val;
    }
};
struct cmp
{
    bool operator ()(Eddge e1, Eddge e2)
    {
        return e1.val>e2.val;
    }
};
priority_queue <Eddge, vector<Eddge>, cmp > Q;
set<int> st;
void init()
{
    st.clear();
    for(int i=1; i<=N; i++) root[i]=i;
    while(!Q.empty()) Q.pop();
}
int fid(int x)
{
    if(root[x] == x) return x;
    return root[x] = fid(root[x]);
}
int Kruskal()
{
    int ans=0;
    while(!Q.empty())
    {
        Eddge now=Q.top();  Q.pop();
        int u=now.nex, v=now.to, cost=now.val;
        int rou=fid(u), rov=fid(v);
        if(rou!=rov)
        {
            root[rou]=rov;
            ans+=cost;
        }
    }
    for(int i=1; i<=N; i++)
    {
        st.insert(fid(i));
    }
    if(st.size()>1) return -1;
    return ans;
}
int main()
{
    int T;  scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &N, &M, &K);
        init();
        while(M--)
        {
            int e1, e2, e3;
            scanf("%d%d%d", &e1, &e2, &e3);
            Q.push(Eddge(e1, e2, e3));
        }
        while(K--)
        {
            int t;
            scanf("%d", &t);
            for(int i=1; i<=t; i++)
            {
                scanf("%d", &a[i]);
                if(i>1)
                {
                    Q.push(Eddge(a[i-1], a[i], 0));
                }
            }
        }
        printf("%d\n", Kruskal());
    }
    return 0;
}