1392: 바 쁜 도시 (city)

【    】
  C           ，           ，                。  C         ：    n     ，             ，                  。        ，                    。          ，             ，       。          ，               ，          ：

1．                           。

2．     1    ，        。

3．     1、2    ，                。

        ，         ，           。

【  】
        n,m     n     ，m   。   m          ，u, v, c      u v       ，   c。(1≤n≤300，1≤c≤10000)。

【  】
    s, max，          ，               。

【    】
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
【    】
3 6

# include 
const int N = 1000 ;
const int M = N * N ;
using namespace std ;
int n , m ;
struct node {
    int u ,v , w ;
}edge[M] ;
bool cmp(node x , node y) {
    return x.w < y.w ;
}
int fa[N] ;
inline int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]) ;
}
inline void merge(int x , int y) {
    fa[x] = y ; return ; 
}
signed main() {
    ios::sync_with_stdio(false) ; 
    cin >> n >> m ;
    for(register int i=1;i<=n;i++) fa[i] = i ;
    for(register int i=1;i<=m;i++) {
        int u , v , w ;
        cin >> u >> v >> w ;
        edge[i] = {u , v , w} ;
    }
    int ans = 0 ; int _max = - 0x7f ;
    sort(edge + 1 , edge + m + 1 , cmp) ;
    for(register int i=1;i<=m;i++) {
        int fx = find(edge[i].u) , fy = find(edge[i].v) ;
        if(fx == fy) continue ;
        merge(fx , fy) ; ans ++ , _max = max(_max , edge[i].w) ;
    }
    printf("%d %d" , ans , _max ) ;
    return 0 ;
}

다음으로 전송:https://www.cnblogs.com/qf-breeze/p/10875057.html