11266: 【原1266】最小差异值

题目描述

author: edly 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1266

Description

P省刚经历一场不小的地震，所有城市之间的道路都损坏掉了，所以省长想请你将城市之间的道路重修一遍。

因为很多城市之间的地基都被地震破坏导致不能修公路了，所以省长给定了你一些城市对，在这些城市对之间可以修公路，并且都有相应的价格。而且因为施工队伍有限，所以省长要求用尽量少的道路将所有的城市连通起来，这样施工量就可以尽量少，道路可视为无向边，且数据保证至少有一种连通的方案。不过，省长为了表示自己的公正无私，要求在满足上述条件的情况下，选择一种方案，使得该方案中最贵道路的价格和最便宜道路的价格的差值尽量小，即使这样的方案会使总价提升很多也没关系。

那么，请你尽快地安排一种合理的方案，满足省长的要求。

Input Format

第一行两个数N，M，表示城市的个数以及可以修的公路数；

第二行开始M行，每行三个数a,b,c，表示a,b之间可以修一条价值c的无向道路。

30%数据满足N<=M<=20

100%数据满足N<=M<=5000，0<c<=50000;

Output Format

一个数表示该方案中最大边减去最小边的值，要求要尽量的小。

Sample Input

Sample Output

1686
(选第4，5，6，9条边即可。)

yyong119's solution

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_N 50010
#define MAX_M 100010

struct node{
    int x, y, c;
} edge[MAX_M];
int n, m;
int par[MAX_N];

inline bool cmp(node p, node q) {
    return p.c < q.c;
}

int find_par(int x) {
    if (par[x] == x) return x;
    par[x] = find_par(par[x]);
    return par[x];
}

int main() {

    scanf("%d%d", &n, &m);
    if (n <= 2) {
        printf("0");
        return 0;
    }
    for (int i = 0; i < m; ++i)
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].c);
    sort(edge, edge + m, cmp);
    int delta_min = 0x7fffffff;
    for (int i = 0; i < m; ++i) {
        for (int j = 1; j <= n; ++j)
            par[j] = j;
        int cnt = 1;
        for (int j = i; j < m && edge[j].c - edge[i].c < delta_min; ++j) {
            int x = find_par(edge[j].x), y = find_par(edge[j].y);
            if (x != y) {
                par[x] = y;
                ++cnt;
                if (cnt == n) {
                    delta_min = edge[j].c - edge[i].c;
                    break;
                }
            }
        }
    }
    printf("%d\n", delta_min);
    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int fa[5005], siz[5005];
int Find(int x){
    return (x == fa[x] ? x: (fa[x] = Find(fa[x])));
}
int Union(int x, int y){
    int u = Find(x), v = Find(y);
    if (u == v) return 0;
    if (siz[u] < siz[v])    
        fa[u] = v, siz[v] += siz[u];
    else
        fa[v] = u, siz[u] += siz[v];
    return 1;
}
struct Edge{
    int u, v, w;
    bool operator < (const Edge& e){
        return w < e.w;
    }
};
Edge e[5005];
void init(){
    n = read(), m = read();
    for (int i = 1; i <= m; ++i)
        e[i].u = read(), e[i].v = read(), e[i].w = read();
    sort(e + 1, e + m + 1);
}
void solve(){
    int ans = INT_MAX;
    for (int i = 1; i <= m; ++i){
        for (int j = 1; j <= n; ++j)
            fa[j] = j, siz[j] = 1;
        int tot = n, cur = i;
        while (cur <= m && tot > 1)
            tot -= Union(e[cur].u, e[cur].v), ++cur;
        if (tot == 1) ans = min(ans, e[cur - 1].w - e[i].w);
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}