讨论 / heap+并查集完美AC
sz136380243 2017-02-28 00:00:35
点我顶贴 收藏 删除
#include <cstdio>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

typedef long long long_long;

struct Revenge

{

int c1, c2;

long_long angry;

};

bool operator< ( struct Revenge a, struct Revenge b )

{

return a.angry < b.angry;

}

void Union( int a, int b, int *Set );

int Find( int a, int *Set );

int main()

{

priority_queue<struct Revenge> heap;

int Set[20001], num, relation, i, j, Enemy[20001];

struct Revenge t;

scanf("%d%d",&num,&relation);

for( i = 1; i <= num; i++ ) Enemy[i] = Set[i] = -1;

for( i = 0; i < relation; i++ ){

scanf("%d%d%lld",&t.c1,&t.c2,&t.angry);

heap.push(t);

}

while( !heap.empty() ){

t = heap.top();

if( Find( t.c1, Set ) == Find( t.c2, Set ) ){

printf("%lld\n",t.angry);

break;

}

if( Enemy[t.c1] != -1 )

Union( t.c2, Enemy[t.c1], Set );

else

Enemy[t.c1] = t.c2;

if( Enemy[t.c2] != -1 )

Union( t.c1, Enemy[t.c2], Set );

else

Enemy[t.c2] = t.c1;

heap.pop();

//cout << t.c1 << " " << t.c2 << " " << t.angry << endl;

}

if( heap.empty() ) printf("0\n");

return 0;

}

void Union( int a, int b, int *Set )

{

int ra = Find( a, Set ),

rb = Find( b, Set );

if( ra == rb ) return;

if( Set[ra] > Set[rb] )

Set[ra] += Set[rb], Set[rb] = ra;

else

Set[rb] += Set[ra], Set[ra] = rb;

}

int Find( int a, int *Set )

{

if( Set[a] < 0 ) return a;

else return Set[a] = Find( Set[a], Set );

}

查看更多回复
提交回复