首页 > 代码库 > hdu--4424--并查集

hdu--4424--并查集

2024-08-07 15:11:35   217人阅读

其实 我觉得这题的难点 不在并查集 而在读懂题目意思

题目给的a b c是表示物资想通过a b路径传输的话 最多只能承载c的大小 意思就是 即使我的物资路线是这样运输的

x-->a--->b   本来<x,a>是运输物资的大小为n 但是a-b只能承载c 那么最终x到达c的时候就只有 c了 这是在基于x>=c的基础上

这边 我们的想法是每次选取边权值最大 因为我们最终的运输量是和最小边的权值有关系。

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 typedef __int64 LL; 6 LL n; 7 const int size = 200010; 8  9 LL dist[size];10 LL father[size] , rank[size];11 struct data12 {13     LL u , v , w;14     bool operator < ( const data& p ) const15     {16         return w > p.w;17     }18 }node[size];19 20 void init( )21 {22     memset( dist , 0 , sizeof(dist) );23     for( int i = 0 ; i<=n ; i++ )24     {25         father[i] = i;26         rank[i] = 1;27     }28 }29 30 LL find( LL x )31 {32     return father[x] == x ? x : father[x] = find( father[x] );33 }34 35 void Union( LL x , LL y , LL len )//将y集合并到x集合中36 {37     father[y] = x;38     rank[x] += rank[y];39     dist[x] = len;40 }41 42 void solve( )43 {44     for( int i = 0 ; i<n-1 ; i++ )45     {46         LL x = find( node[i].u );47         LL y = find( node[i].v );48         LL len1 = dist[x] + rank[y] * node[i].w;49         LL len2 = dist[y] + + rank[x] * node[i].w;50         if( len1>=len2 )51         {52             Union( x , y , len1 );53         }54         else55         {56             Union( y , x , len2 );57         }58     }59 }60 61 int main()62 {63     cin.sync_with_stdio(false);64     while( cin >> n )65     {66         init( );67         for( int i = 0 ; i<n-1 ; i++ )68         {69             cin >> node[i].u >> node[i].v >> node[i].w;70         }71         sort( node , node+n-1 );72         solve( );73         cout << dist[ find(1) ] << endl;74     }75     return 0;76 }
View Code

 

hdu--4424--并查集


联系
我们