# Connecting Cities with the Minimum Product of Costs
(Time Limit: 1 second)

The ACM kingdom has n cities, numbered from 0 to n − 1. An (unordered) pair $(i, j) ∈ {0, 1, . . . , n − 1}^2$ of distinct cities is said to be linkable if we are able to build a road linking i and j. It is guaranteed that if we build a road between i and j for all linkable pairs $(i, j) ∈ {0, 1, . . . , n − 1}^2$, then any two distinct cities will be reachable (via one or more roads) from each other. For every linkable pair $(i, j) ∈ {0, 1, . . . , n − 1}^2$, denote by $cij ≥ 0$ the cost of building a road between i and j. Mr. Smart wants to build roads with the minimum product of costs subject to every city being reachable from every other city. Please help him.
## Technical Specification
1. There are at most 10 test cases.
2. 2 ≤ n ≤ 500.
3. There are at most 25000 linkable pairs.
4. For every linkable pair $(i, j) ∈ {0, 1, . . . , n − 1}^2, cij ∈ {0, 1, . . . , 999}$.
## Input Format
Each test case begins with n and then the number of linkable pairs. Every linkable pair $(i, j) ∈ {0, 1, . . . , n − 1}^2$ is specified by i, j and ci,j , in that order. Furthermore, any two consecutive integers are separated by whitespace character(s). The last test case is “0 0”, which shall not be processed.
## Output Format
Do the following for each test case: Denoting by C the minimum product of costs subject to every city being reachable from every other city, please output the remainder of the division of C by 65537, i.e., C mod 65537.
## Sample Input
4 5
0 2 996
1 0 3
1 2 4
2 3 800
1 3 998
3 3
10 2 500
0 1 0
1 2 600
5 7
0 1 100
0 2 999
1 2 100
1 3 10
2 3 100
3 4 58
4 1 999
0 0
## Sample Output for the Sample Input
9600
0
32744
## 看題目送code
我人真好～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Set{
    Set* parent;
    int rank;
};

struct Edge{
    int a;
    int b;
    int weight;
};

bool compare(Edge a, Edge b){
    return a.weight < b.weight;
}

Set* find_set(Set *x)
{
    if(x!=x->parent)//if x!=x.p
        x->parent = find_set(x->parent);
    return x->parent;
}

void link(Set *a, Set *b)
{
    if(a->rank > b->rank)
        b->parent = a;
    else 
    {
        a->parent=b;
        if(a->rank==b->rank)
            b->rank = b->rank+1;
    }
}

void uniset(Set *a, Set *b)
{
    link(find_set(a),find_set(b));
}

int Kruskal(vector<Edge>&E) // (G,w)
{
    int answer = 1;
    vector<int>A;//A = null set
    vector<Set> s(E.size());
    for(int i=0;i<s.size();i++) // for each v belongs to G.V
    {
        s[i].parent = &s[i]; 
        s[i].rank = 0;
    }
    //sort the edges of G.E into nondecreasing order by weight w
    for(int i=0;i<E.size();i++)//for each edge (u, v) belongs to G.E, taken in nondecreasing order by weight
    {
        if(find_set(&s[E[i].a])!=find_set(&s[E[i].b]))//if FIND-SET(u) != FIND-SET(v)
        {
            // A = A belongs to {(u, v)}
            uniset(&s[E[i].a],&s[E[i].b]);// UNION(u, v)
            answer = (answer*(E[i].weight))%65537;
        }
    }
    return answer;
}

int main()
{
    int citys, roads, counter=0;
    int answer[500];
    while(cin>>citys>>roads&&citys!=0){
        vector<Edge> E(roads);
        for(int i=0;i<roads;i++)
            cin >> E[i].a >> E[i].b >> E[i].weight;
        sort(E.begin(),E.end(),compare);
        answer[counter] = Kruskal(E);
        counter++;
    }
    for(int i=0;i<counter;i++)
        cout << answer[i] << endl;
    return 0;
}

###### tags:`演算法` `cpp` `Awwwolf的刷題之路`