学步园

zoj 2677 

题意：给你n个点，m条边，钱数s。要你破坏尽量多的管道，破坏每个管道都会付出一些钱。并且要使得这个图仍然连通。

分析：先求出最大生成树，然后把剩下的边从小到大排序，依次取最小的（用优先队列 或 小顶堆），取到钱用完为止。

prim算法是对 点的操作。而Krusckal算法是对边操作。

这题用prim算法 求的话，矩阵为超内存，且不好处理边。

Kruskal 算法：由 1.并查集，2.优先队列 或 堆 组成。

每次 取（最小或最大） 的边加入并查集， 就构成了（最小或最大）生成树。

转载代码。。。当然并查集部分 可以压缩路径.

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

#define MAXN 51011
#define MAX_PRICE 1<<30

struct Edge
{
    int x,y;
    int price;
    int id;
    bool operator<(const Edge& rhs)const{
        return price<rhs.price;
    }
    bool operator>(const Edge& rhs)const{
        return price>rhs.price;
    }
};

priority_queue<Edge> que;
priority_queue<Edge,vector<Edge>,greater<Edge> > result;
int parent[MAXN];
int op[MAXN*2];
int n;
int m;
int fund;
int sum;
void init()
{
    for (int i=1;i<=n;i++){
        parent[i] = -1;
    }
    Edge edge;
    for (int i=1;i<=m;i++){
        scanf("%d %d",&edge.x,&edge.y);
        scanf("%d",&edge.price);
        edge.id = i;
        que.push(edge);
    }
}

int find(int x)
{
    if (parent[x]!=-1)
        return find(parent[x]);
    else return x;
}

void Kruskal()
{
    while(!que.empty()){
        Edge edge(que.top());
        //cout<<"-----"<<edge.x<<"  "<<edge.y<<"  "<<edge.price<<endl;
        que.pop();
        int fa,fb;
        fa = find(edge.x);
        fb = find(edge.y);
        if (fa!=fb){
            parent[fb] = fa;
        }
        else
        {
            result.push(edge);
        }
    }
    int sum = 0;
    int ct = 0;
    while(!result.empty()){
        Edge edge(result.top());
        result.pop();

        sum+=edge.price;
        if (sum<=fund){
            op[ct++]=edge.id;
        }
        else
            break;
    }
    printf("%d\n",ct);
    if (ct!=0){
        for (int i=0;i<ct-1;i++)
            printf("%d ",op[i]);
        printf("%d\n",op[ct-1]);
    }
}


int main()
{
    int ct=0;
    while(scanf("%d %d %d",&n,&m,&fund)!=EOF){
        if (ct==0)
            ct++;
        else
            printf("\n");

        while(!que.empty())que.pop();
        while(!result.empty())result.pop();
        init();
        Kruskal();
    }
    return 0;
}