贪心 + 并查集 之 CODE[VS] 1069 关押罪犯 2010年NOIP全国联赛提高组

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 #include <cstddef>
  5 #include <iterator>
  6 #include <algorithm>
  7 #include <string>
  8 #include <locale>
  9 #include <cmath>
 10 #include <vector>
 11 #include <cstring>
 12 #include <map>
 13 #include <utility>
 14 #include <queue>
 15 #include <stack>
 16 #include <set>
 17 #include <functional>
 18 using namespace std;
 19 typedef pair<int, int> P; 
 20 const int INF = 0x3f3f3f3f;
 21 const int modPrime = 3046721;
 22 const double eps = 1e-9;
 23 const int MaxN = 20010;
 24 const int MaxM = 100010;
 25 
 26 int N, M;
 27 struct Node
 28 {
 29     int a, b, c;
 30 };
 31 
 32 Node nodeVec[MaxM];
 33 
 34 bool Cmp(const Node n1, const Node n2)
 35 {
 36     return n1.c > n2.c;
 37 }
 38 
 39 /**************************************/
 40 //Union-Find Sets
 41 
 42 int ftr[MaxN << 1];
 43 
 44 void ufsIni(int n)
 45 {
 46     for (int i = 0; i <= n; ++i)
 47     {
 48         ftr[i] = i;
 49     }
 50 }
 51 
 52 int ufsFind(int x)
 53 {
 54     if (x == ftr[x])
 55     {
 56         return x;
 57     }
 58     return ftr[x] = ufsFind(ftr[x]);
 59 }
 60 /**************************************/
 61 
 62 
 63 void Solve()
 64 {
 65     int ans = 0;
 66     ufsIni((N << 1));
 67     int x, y;
 68     for (int i = 0; i < M; ++i)
 69     {
 70         x = ufsFind(nodeVec[i].a);
 71         y = ufsFind(nodeVec[i].b);
 72         if (x == y)
 73         {
 74             ans = nodeVec[i].c;
 75             break;
 76         }
 77         ftr[x] = ufsFind(nodeVec[i].b + N);
 78         ftr[y] = ufsFind(nodeVec[i].a + N);
 79     }
 80     printf("%d\n", ans);
 81 }
 82 
 83 int main()
 84 {
 85 #ifdef HOME
 86     freopen("in", "r", stdin);
 87     //freopen("out", "w", stdout);
 88 #endif
 89     
 90     scanf("%d %d", &N, &M);
 91     for (int i = 0; i < M; ++i)
 92     {
 93         scanf("%d %d %d", &nodeVec[i].a, &nodeVec[i].b, &nodeVec[i].c);
 94     }
 95     sort(nodeVec, nodeVec + M, Cmp);
 96     Solve();
 97 
 98 #ifdef HOME
 99     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
100     _CrtDumpMemoryLeaks();
101 #endif
102     return 0;
103 }