最近考试【最小差异值】这个问题出现次数还蛮多的，之前思路想错了，直接报 0（额……就是打 0 分的意思啊），这次考试才终于 AC 掉了。
先上问题吧。
最小差异值
【问题描述】
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;
嗯，看完题目，先忍住心中莫名的怒火（这省长真是聪 (zhi) 明 (zhang) 为什么不选最便宜的路径（那样就可以直接最小生成树了呀）修路啊！真是……），分析一下题目。
要路的条数最少，那路的条数就是 N（城市数目）-1，说白了就是要你生成一棵树。
还要求最大费用路和最小费用路的差最小。怎么让路与路之间的费用差最小呢？看看下面：
按输入样例来看：
路的费用：
9384
887
2778
6916
7794
8336
5387
493
6650
1422
这样子无序地排列，差值会比较大。
其实用数学的思维想一想就知道了，当路已经按照费用排好序的时候，它们之间的差会是最小的：
493
887
1422
2778
5387
6650
6916
7794
8336
9384
这样排序以后，差值不就是最小的了吗？（实在不好解释啊，额，真的，用数学的思维想一想啊！）
这里的排序从小到大还是从大到小排序都是一样的，但是后面我们都以从小到大排序来讲。
排好序了怎么办呢？
其实我也不知道啊，啊哈哈哈哈。我这里用的是枚举，比如这里，就从排好序的第一条路开始，一直到第 M-N+1 条路（为什么是 M-N+1 呢？后面会讲的。），枚举出来，以这条枚举出来的路为生成树的第一条边生成一棵树。额，讲不清楚，上图算了：
以此类推。现在知道为什么只枚举到第 M-N+1 条路了吗？对啊，如果目前枚举的这条路加上剩下的所有路的条数小于了 N-1 条，比如在样例中，你枚举到了第 7 条（7794），然后你用 3 条边生成一个有 5 个节点的树肯定是不行的。
最后把保存下来的最小费用差输出即可！
贴上满分代码（又开始飘了）：
#include <iostream>
#include <iomanip>
using namespace std;
int n,m,fa[5005];
struct side * head=NULL;
struct side{
int data;
int n1,n2;
struct side * next;
};
void addside(int a,int b,int c)//加入边的函数
{
struct side * p=new struct side;
p->data=c;
p->n1=a;
p->n2=b;
if(head==NULL)
{
head=p;
head->next=NULL;
return;
}
if(c>=head->data)
{
p->next=head;
head=p;
return;
}
struct side * q=head;
while(q->next!=NULL)
{
if(c>=q->next->data)
{
p->next=q->next;
q->next=p;
return;
}
q=q->next;
}
q->next=p;
p->next=NULL;
return;
}
int find(int x)//并查集函数
{
if(fa[x]==x)return x;
fa[x]=find(fa[x]);
return fa[x];
}
bool conside(struct side * a)//连边，成功返回 true
{
if(find(a->n1)!=find(a->n2))
{
fa[find(a->n2)]=fa[find(a->n1)];
return true;
}
else
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
addside(a,b,c);
}
struct side * p=head;
struct side * q;
int ans=999999999,min,max,count;
for(int i=1;i<=m-n+2;i++)
{
min=999999999;max=-1;count=0;
q=p;
for(int j=1;j<=n;j++)
fa[j]=j;
while(q!=NULL)
{
if(conside(q)==true)
{
count++;
if(q->data<min)min=q->data;
if(q->data>max)max=q->data;
}
q=q->next;
}
if(count==n-1)
if(max-min<ans)
ans=max-min;
p=p->next;
}
cout<<ans;
return 0;
}
0 条评论