首页 > 代码库 > T4 最小差异值 dvalue

T4 最小差异值 dvalue

2024-08-15 21:26:55   218人阅读

 

T4 最小差异值 dvalue

 

【问题描述】

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

【输入格式】

　　第一行两个数 N,M,表示城市的个数以及可以修的公路数;
　　第二行开始 M 行,每行三个数 a,b,c,表示 a,b 之间可以修一条价值 c 的无向
道路。

【输出格式】

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

【样例输入】

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

【样例输出】

1686

【样例说明】
选第 4,5,6,9 条边即可。
【数据说明】
30%数据满足 N<=M<=20
100%数据满足 N<=M<=5000,0<c<=50000;

Solution

最小生成树,最小瓶颈生成树

①m^2

将边排序,枚举一个下界(上界),做最小生成树(不连通即可退出),

②mlogm

二分一个

Code

// <dvalue.cpp> - Thu Oct  6 08:17:54 2016// This file is made by YJinpeng，created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#define MOD 1000000007#define INF 1e9#define IN inline#define RG registerusing namespace std;typedef long long LL;typedef long double LB;const int MAXN=5010;const int MAXM=100010;inline int max(int &x,int &y) {return x>y?x:y;}inline int min(int &x,int &y) {return x<y?x:y;}inline int gi() {	register int w=0,q=0;register char ch=getchar();	while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar();	if(ch==‘-‘)q=1,ch=getchar();	while(ch>=‘0‘&&ch<=‘9‘)w=w*10+ch-‘0‘,ch=getchar();	return q?-w:w;}struct edge{    int u,v,w;    bool operator<(edge a)const{return w<a.w;}}e[MAXM];int f[MAXN],ans;IN int find(int x){return x==f[x]?x:f[x]=find(f[x]);}void pri(){printf("%d",ans);exit(0);}int main(){	freopen("dvalue.in","r",stdin);	freopen("dvalue.out","w",stdout);    int n=gi(),m=gi(),M=0;ans=INF;    for(int i=1;i<=m;i++)e[i]=(edge){gi(),gi(),gi()};    sort(e+1,e+1+m);    for(int i=1;i<=m;i++){        for(int j=1;j<=n;j++)f[j]=j;        for(int j=i;j<=m;j++)            if(find(e[j].u)!=find(e[j].v)){                M=e[j].w;f[f[e[j].u]]=f[e[j].v];            }        find(1);int x=f[1];        for(int j=2;j<=n;j++){            find(j);if(f[j]!=x)pri();        }        ans=min(ans,M-e[i].w);    }pri();	return 0;}

　　

 

T4 最小差异值 dvalue


联系
我们