POJ 1861 Network

这题就是用最小生成树中的kruskal算法的模板题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1002;
const int M=15002;
const int inf=1<<28;
struct edge
{
    int u,v,cost;
}es[M];
int father[N],deep[N];
int n,m;
void init()
{
    for(int i=0;i<N;i++)
    {
        father[i]=i;
        deep[i]=0;
    }
}
int find_father(int x)
{
    if(x!=father[x])
        father[x]=find_father(father[x]);
    return father[x];
}
bool _merge(int a,int b)
{
    int x=find_father(a);
    int y=find_father(b);
    if(x==y)
        return true;
    if(deep[x]<deep[y])
        father[x]=y;
    else
    {
        if(deep[x]==deep[y])
            deep[x]++;
        father[y]=x;
    }
    return false;
}
bool cmp(edge a,edge b)
{
    return a.cost<b.cost;
}
void kruskal()
{
    int cnt=0,_max=0;
    queue<int> q;
    init();
    for(int i=1;i<=m;i++)
    {
        if(!_merge(es[i].u,es[i].v))
        {
            cnt++,q.push(i);
            if(_max<es[i].cost)
                _max=es[i].cost;
        }
        if(cnt==n-1)
            break;
    }
    printf("%d\n",_max);
    int len=q.size();
    printf("%d\n",len);
    for(int i=0;i<len;i++)
    {
        int id=q.front();
        q.pop();
        printf("%d %d\n",es[id].u,es[id].v);
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);
        sort(es+1,es+m+1,cmp);
        kruskal();
    }
    return 0;
}