P2330-[SCOI2005]繁忙的都市

墨蓝 2023-06-01 08:55 20阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define pb push_back
     4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
     5 #define INF 100000003
     6 #define ll long long
     7 inline ll read()
     8 {
     9     ll ans = 0;
    10     char ch = getchar(), last = ' ';
    11     while(!isdigit(ch)) last = ch, ch = getchar();
    12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    13     if(last == '-') ans = -ans;
    14     return ans;
    15 }
    16 inline void write(ll x)
    17 {
    18     if(x < 0) x = -x, putchar('-');
    19     if(x >= 10) write(x / 10);
    20     putchar(x % 10 + '0');
    21 }
    22 int n;
    23 int mincost[303];
    24 bool used[303];
    25 struct edge
    26 {
    27     int to,cost;
    28 };
    29 vector<edge> G[303];
    30 int V,E;
    31 int maxx = 0;
    32 int minn = INF;
    33 int MST(int K)
    34 {
    35     _for(i,1,V+1)
    36     {
    37         mincost[i] = INF;
    38         used[i] = false;
    39     }
    40 
    41     mincost[1] = 0;
    42     int res = 0;
    43 
    44     while(1)
    45     {
    46         int v = -1;
    47         _for(u,1,V+1)
    48         if(!used[u] && (v==-1 || mincost[u] < mincost[v]))
    49             v = u;
    50         
    51         if(v==-1) break;
    52         used[v] = true;
    53         res += mincost[v];
    54 
    55         _for(u,0,G[v].size())
    56             if(G[v][u].cost<=K)
    57                 mincost[G[v][u].to] = min(mincost[G[v][u].to],G[v][u].cost);
    58     }
    59     return res;
    60 }
    61 bool C(int d)
    62 {
    63     if(MST(d)>=INF)
    64         return false;
    65     return true;
    66 }
    67 int solve()
    68 {
    69     int lb = minn,ub = maxx;
    70     while(ub - lb > 1)
    71     {
    72         int mid =  lb+(ub-lb)/2;
    73         if(C(mid)) ub = mid;
    74         else lb = mid;
    75     }
    76 
    77     if(!C(lb))
    78         return lb+1;
    79     return lb;
    80 }
    81 
    82 int main()
    83 {
    84     V = read(),E = read();
    85     _for(i,0,E)
    86     {
    87         int a,b,c;
    88         a = read(),b = read(), c = read();
    89         G[a].push_back({b,c});
    90         G[b].push_back({a,c});
    91         maxx = max(maxx,c);
    92         minn = min(minn,c);
    93     }
    94 
    95     int rnt = solve();
    96     printf("%d %d",V-1,rnt);
    97     return 0;
    98 }

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