# 11266: 【原1266】最小差异值

### 题目描述

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

## Description

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

## Input Format

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

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

## Sample Input

``````5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422
``````

## 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 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(){
for (int i = 1; i <= m; ++i)
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;
}
``````