P1111-修复公路

以你之姓@ 2023-06-01 08:55 32阅读 0赞

1 #include <bits/stdc++.h>
      2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      4 #define INF 0x3f3f3f3f
      5 #define MOD 1000000007
      6 typedef long long ll;
      7 using namespace std;
      8 inline ll read()
      9 {
     10     ll ans = 0;
     11     char ch = getchar(), last = ' ';
     12     while(!isdigit(ch)) last = ch, ch = getchar();
     13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     14     if(last == '-') ans = -ans;
     15     return ans;
     16 }
     17 inline void write(ll x)
     18 {
     19     if(x < 0) x = -x, putchar('-');
     20     if(x >= 10) write(x / 10);
     21     putchar(x % 10 + '0');
     22 }
     23 
     24 const int maxn = 100039;
     25 int par[maxn];
     26 int high[maxn];
     27 int cnt;
     28 void init(int n)
     29 {
     30     _for(i,1,n+1)
     31     {
     32         par[i] = i;
     33         high[i] = 0;
     34     }
     35     cnt = n-1;
     36 }
     37 
     38 int find(int x)
     39 {
     40     return par[x] == x ? x : par[x] = find(par[x]);
     41 }
     42 
     43 void unite(int x,int y)
     44 {
     45     x = find(x);
     46     y = find(y);
     47     if(x==y) return ;
     48     cnt --;
     49     if(high[x]<high[y])
     50         par[x] = y;
     51     else
     52     {
     53         par[y] = x;
     54         if(high[x]==high[y])
     55             high[x] ++;
     56     }
     57 }
     58 
     59 bool same(int x,int y)
     60 {
     61     return find(x) == find(y);
     62 }
     63 int N,M;
     64 struct edge
     65 {
     66     int from;
     67     int to;
     68     int cost;
     69     bool operator < (edge b)
     70     {
     71         return this->cost<b.cost;
     72     }
     73 };
     74 edge x[maxn];
     75 bool C(int d)
     76 {
     77     init(N);
     78     _for(i,1,M+1)
     79         if(d>=x[i].cost)
     80             unite(x[i].from,x[i].to);
     81     return cnt == 0;
     82 }
     83 int solve()
     84 {
     85     sort(x+1,x+M+1);
     86     int lb = 0,ub = 110000;
     87     while(lb < ub)
     88     {
     89         int mid =  lb+(ub-lb)/2;
     90         if(C(mid)) ub = mid;
     91         else lb = mid+1;
     92     }
     93     return lb;
     94 }
     95 
     96 int main()
     97 {
     98     N = read(), M = read();
     99     int maxx;
    100     _for(i,1,M+1)
    101     {
    102         x[i].from = read();
    103         x[i].to = read();
    104         x[i].cost = read();
    105         maxx = max(maxx,x[i].cost);
    106     }
    107     int rnt = solve();
    108     if(rnt>maxx)
    109         printf("-1\n");
    110     else
    111         printf("%d\n",rnt);
    112     return 0;
    113 }

转载于:https://www.cnblogs.com/Asurudo/p/11548616.html