一个最小生成树的题目,用并查集判连通。地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1679
#include <stdio.h>
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 105;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int b;
int e;
int len;
int flag;
}seg[LEN*LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp ( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return *( ( int * )a + 2 ) - *( ( int * )b + 2 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int p[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void make ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[i] = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find ( int a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( p[a] < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int r = find ( p[a] );
p[a] = r;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return r;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void un ( int a, int b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ra = find ( a );
int rb = find ( b );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( p[ra] < p[rb] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[ra] += p[rb];
p[rb] = ra;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[rb] += p[ra];
p[ra] = rb;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int temp[LEN];
int pt;
int data[LEN];
int pd;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int kul ( int n, int m, int *ans )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
*ans = 0;
pt = 0;
make ( n );
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( seg[i].flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
seg[i].flag = 0;
continue;
}
if ( find ( seg[i].b ) != find ( seg[i].e ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
un ( seg[i].b, seg[i].e );
*ans = *ans + seg[i].len;
temp[pt++] = i;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int r = find ( 0 );
for ( i=1; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( find ( i ) != r )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
if ( i < n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return 0;
}
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t;
int n, m;
int b, e, len;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf ( "%d", &t );
while ( t -- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d%d", &n, &m );
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf ( "%d%d%d" , &b, &e, &len );
seg[i].b = b-1;
seg[i].e = e-1;
seg[i].len = len;
seg[i].flag = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort ( seg, m, sizeof ( seg[0] ), cmp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int min;
kul ( n, m, &min );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<pt; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
data[i] = temp[i];
}
pd = pt;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<pd; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int temp;
seg[ data[i] ].flag = 1;
if ( kul ( n, m, &temp ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( temp == min )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
break;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( i >= pd )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "%d\n", min );
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "Not Unique!\n" );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)