zju2281 -- way to freedom(b).cpp

Zhejiang University Online Judge 第2277题至第2283题的代码和解题报告

// PROB         Zju Online Judge 2281 -- Way to Freedom
// Algorithm    Greedy + Disjoint
// Complexity   O (MlogM + Mlog*N)
// Author       LoveShsean
// Comment      I'm lazy. You can improve this code 
//              by using heap or sort-divide. :)
#include <stdio.h>
#include <algorithm>

#define maxn 100010
#define maxm 1001000

using namespace std;

int eu [maxm], ev [maxm], ew [maxm], id [maxm], M;
int pnt [maxn], rank [maxn], N;
int src, dst;

bool cmp (const int &x, const int &y)
{
    return ew [x] > ew [y];
}

int find (int x)
{
    if (pnt [x] != x) pnt [x] = find (pnt [x]);
    return pnt [x];
}

int main ()
{
    int i, j, x, y;
    while (scanf ("%d%d", &N, &M) == 2)
    {
        for (i = 0; i < M; i ++)
            id [i] = i, scanf ("%d%d%d", eu + i, ev + i, ew + i);
        scanf ("%d%d", &src, &dst);

        sort (id, id + M, cmp);
        for (i = 1; i <= N; i ++) rank [pnt [i] = i] = 0;

        for (i = 0; i < M; i ++)
        {
            j = id [i]; x = find (eu [j]); y = find (ev [j]);

            if (rank [x] > rank [y]) pnt [y] = x;
            else pnt [x] = y, rank [y] += (rank [x] == rank [y]);

            if (find (src) == find (dst)) break;
        }
        if (i == M) printf ("0\n"); 
        else printf ("%d\n", ew [j]);
    }
    return 0;
}