【codeforces】gym 101137 K - Knights of the Old Republic【用最小生成树对图做集合dp】

本文主要是介绍【codeforces】gym 101137 K - Knights of the Old Republic【用最小生成树对图做集合dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：【codeforces】gym 101137 K - Knights of the Old Republic

考虑对图集合dp，一个连通块的dp值为两个连通块的值的和或者强制加一条新边后的最小值，取个最小值（边从小到大枚举，则强制加一条最大的边会导致连通块内较小的边一定都选，则会构成一个生成树）。用kruskal实现这个dp过程即可。

#include <bits/stdc++.h>
using namespace std ;typedef long long LL ;const int MAXN = 300005 ;struct Edge {int u , v , c ;bool operator < ( const Edge& a ) const {return c < a.c ;}
} ;Edge E[MAXN] ;
int a[MAXN] , b[MAXN] , p[MAXN] ;
LL sum[MAXN] ;
int n , m ;int F ( int x ) {return p[x] == x ? x : ( p[x] = F ( p[x] ) ) ;
}void solve () {for ( int i = 1 ; i <= n ; ++ i ) {p[i] = i ;}for ( int i = 1 ; i <= n ; ++ i ) {scanf ( "%d%d" , &a[i] , &b[i] ) ;sum[i] = 1LL * a[i] * b[i] ;}for ( int i = 0 ; i < m ; ++ i ) {scanf ( "%d%d%d" , &E[i].u , &E[i].v , &E[i].c ) ;}sort ( E , E + m ) ;for ( int i = 0 ; i < m ; ++ i ) {int x = F ( E[i].u ) ;int y = F ( E[i].v ) ;if ( x == y ) continue ;int na = max ( max ( a[x] , a[y] ) , E[i].c ) ;int nb = min ( b[x] , b[y] ) ;LL tmp = 1LL * na * nb ;sum[y] = min ( sum[x] + sum[y] , tmp ) ;p[x] = y ;a[y] = na ;b[y] = nb ;}LL ans = 0 ;for ( int i = 1 ; i <= n ; ++ i ) {if ( F ( i ) == i ) ans += sum[i] ;}printf ( "%lld\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;return 0 ;
}