2017 第11次CCF-CSP认证 地铁修建-并查集

              这道题得满分的数据范围还是比较大的，不能直接DFS扫，正解应该是并查集，每一次添加最小的一条边，直到结点1和结点n连通为止。代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;//并查集 
typedef struct Edge{
int a, b;
int v;
}Edge;
Edge e[200010];
int n, m;
int pre[100010];

bool cmp(const Edge &a, const Edge &b)
{
return a.v < b.v;
}

int find(int x)
{
if(pre[x] == x)
   return x;
else
   return pre[x] = find(pre[x]);
}

void join(int a, int b)
{
int fa = find(a), fb = find(b);
pre[fa] = fb;
}


int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].v);
}
sort(e+1, e+m+1, cmp);
for(int i = 1; i <= n; i++)
   pre[i] = i;
for(int i = 1; i <= m; i++)
{
   int fa = find(e[i].a), fb = find(e[i].b);
   if(fa != fb)
      join(e[i].a, e[i].b);
   int f1 = find(1), fn = find(n);
   if(find(1) == find(n))
   {
      printf("%d\n", e[i].v);
      break;
   }
}
return 0;
}