http://118.190.20.162/view.page?gpid=T54

 

Idea: Using the method of union search, all edges are sorted from small to large, and the smallest edges are selected continuously until the first node and the last node are connected (that is, their ancestors are the same). The corresponding number of days (weights) on the output side is required.

 

Problem Description

There are n transportation hubs in A city, among which No. 1 and No. n are very important. In order to strengthen transportation capacity, A city decided to build a subway between No. 1 and No. n hubs.
The subway consists of many sections of tunnels, each of which connects two transportation hubs. After exploration, there are m-section tunnels as candidates. At most, there is only one candidate tunnel between the two traffic hubs, and no tunnel ends are connected to the same traffic hub.
At present, there are n companies that construct tunnels, each candidate tunnel can only be constructed by one company, each company needs the same number of days to construct. Each company can only build one candidate tunnel at most. All companies started construction at the same time.
As the project manager, you have obtained information about the candidate tunnels. Now you can choose some tunnels to construct according to your own ideas. How many days will it take to build the whole subway?

Input format

The first line of input contains two integers n and m, separated by a space, representing the number of traffic hubs and the number of candidate tunnels, respectively.
Lines 2 to m+1, each line contains three integers a, b, c, indicating that a tunnel can be built between hub A and hub B in a time of C days.

Output format

Output an integer, the minimum number of days needed to build the entire subway line.

sample input

6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6

sample output

6

Sample description

There are two kinds of routes that can be built.
The first type of transit hub is 1, 2, 3, 6 in turn. The time required is 4, 4 and 7, respectively. The whole subway line needs 7 days to be repaired.
The second type of transit hub is 1, 4, 5, 6 in turn. The time required is 2, 5 and 6, respectively. The whole subway line needs 6 days to be repaired.
The second scheme uses fewer days.

Assessment of use case size and conventions

For 20% of the evaluation cases, 1 < n < 10, 1 < m < 20;
For 40% of the evaluation cases, 1 < n < 100, 1 < m < 1000;
For 60% of the test cases, 1 < n < 1000, 1 < m < 10000, 1 < c < 1000;
For 80% of the test cases, 1 < n < 10000, 1 < m < 100000;
For 100% of the evaluation cases, 1 < n < 100000, 1 < m < 200000, 1 < a, b < n, 1 < c < 1000000.

All evaluation cases ensure that Hub 1 can reach all other hubs through the tunnel when all candidate tunnels are completed.

 

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>

#define LL long long
int const MAX = 1e6 + 11;
int const INF = 1 << 30;

using namespace std;
struct Node {
    int start, end, val;
    Node() {
    }
    Node(int s, int e, int v) : start(s), end(e), val(v) {
    }
};

int father[MAX];
int n, m;
//Edges are twice as large as nodes.
Node g[2 * MAX];

inline int cmp(const Node& a, const Node& b) {
    return a.val < b.val;
}

inline int findFather(int son) {
    int t = son;

    while ( son != father[son] ) {
        son = father[son];
    }
    //Path Compression
    while ( t != father[t] ) {
        int m = t;
        father[m] = son;
        t = father[m];
    }

    return son;
}

inline void Union ( int x, int y ) {
    int fx = findFather(x), fy = findFather(y);

    if ( fx != fy )
        father[fx] = fy;
}

int main(int argc, char*argv[]) {
    scanf("%d %d", &n, &m);
    for ( int i = 1; i <= m; i++ ) {
        scanf("%d %d %d", &g[i].start, &g[i].end, &g[i].val);

    }
    sort(g + 1, g + 1 + m, cmp );

    //Initialization and collection
    for ( int i = 1; i <= m; i++ ) {
        father[i] = i;
    }


    for ( int i = 1; i <= m; i++ ) {
        int st = g[i].start, ed = g[i].end;
        if ( findFather(st) == findFather(ed) )
            continue;


        Union(st, ed);

        if ( findFather(1) == findFather(n) ) {
            printf("%d\n", g[i].val);
            break;
        }
    }


    return 0;
}

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;//And collect
typedef struct Edge {
    int a, b;
    int v;
} Edge;
Edge e[200010];
int n, m;
int pre[100010];

bool cmp(const Edge &a, const Edge &b) {
    return a.v < b.v;
}

int find(int x) {
    if ( pre[x] == x )
        return x;
    else
        return pre[x] = find(pre[x]);
}

void join(int a, int b) {
    int fa = find(a), fb = find(b);

    pre[fa] = fb;
}


int main() {
    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= m; i++ ) {
        int a, b, c;
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].v);
    }
    sort(e + 1, e + m + 1, cmp);
    for ( int i = 1; i <= n; i++ )
        pre[i] = i;
    for ( int i = 1; i <= m; i++ ) {
        int fa = find(e[i].a), fb = find(e[i].b);
        if ( fa != fb )
            join(e[i].a, e[i].b);
        int f1 = find(1), fn = find(n);
        if ( find(1) == find(n) ) {
            printf("%d\n", e[i].v);
            break;
        }
    }
    return 0;
}