学步园

题意：有n（1<=n<=2000）个城市，每个城市之间有不同的航空公司的航线k（1<=k<=200000）相连，每条航线有一定的费用，航空公司有

          m（1<=m<=2000）个，现在想只保留一个航空公司，为了使得任意两个城市都能直接或者间接相连接，这样就需要收购其他公司掌控的一些航线，

          但是需要花费相应的费用，问最少需要花费多少费用。

题解：这个题需要对最小生成树的边的性质有很好的理解，在最小生成树中任意一条边都是连接两个集合边权最小的一条边。首先枚举航空公司是肯定的，

          那么怎样高效枚举出其他边呢？首先搞出最小生成树，然后然后枚举航空公司，然后再枚举在最小生成树中不属于当前航空公司的边即可，具体见代码。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
const int inf = 1 << 29;
const int maxn = 2002;
const int maxe = 200002;
struct air
{
    int id,u,v,c,p;
    bool operator < (const air &other) const
    {
        return p < other.p;
    }
}ai[maxe];
struct node
{
    int u,v,w;
    int next;
}edge[maxe];
int head[maxn],father[maxn],ans[maxn],at[maxn];
int m,n,k,idx,top;

int find(int u)
{
    return (u == father[u]) ? father[u] : (father[u] = find(father[u]));
}

void init()
{
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
    }
    idx = top = 0;
    return;
}

void addedge(int num,int u,int v,int w)
{
    edge[idx].u = u;
    edge[idx].v = v;
    edge[idx].w = w;
    edge[idx].next = head[num];
    head[num] = idx++;
    return;
}

void read()
{
    for(int i=0;i<k;i++)
    {
        ai[i].id = i+1;
        scanf("%d %d %d %d",&ai[i].u,&ai[i].v,&ai[i].c,&ai[i].p);
        addedge(ai[i].c , ai[i].u , ai[i].v , ai[i].p);
    }
    sort(ai , ai + k);
    return;
}

void kruskal()
{
    for(int i=0;i<k;i++)
    {
        int x = find(ai[i].u);
        int y = find(ai[i].v);
        if(x != y)
        {
            ai[top++] = ai[i];
            father[y] = x;
        }
    }
    return;
}

void inital(int st)
{
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
    }
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        int x = find(edge[i].u);
        int y = find(edge[i].v);
        father[y] = x;
    }
    return;
}

void solve()
{
    int sum = inf,bj,num;
    for(int i=1;i<=m;i++)
    {
        inital(i);
        int res = 0,c = 0;
        for(int j=0;j<top;j++)
        {
            int x = find(ai[j].u);
            int y = find(ai[j].v);
            if(x != y)
            {
                father[y] = x;
                res += ai[j].p;
                at[c++] = ai[j].id;
            }
        }
        if(res < sum)
        {
            sum = res;
            bj = i;
            num = c;
            for(int j=0;j<c;j++)
            {
                ans[j] = at[j];
            }
        }
    }
    printf("%d %d %d\n",sum,bj,num);
    for(int i=0;i<num;i++)
    {
        printf("%d\n",ans[i]);
    }
    return;
}

int main()
{
    while(~scanf("%d %d %d",&n,&m,&k))
    {
        init();
        read();
        kruskal();
        solve();
    }
    return 0;
}