最近考试【最小差异值】这个问题出现次数还蛮多的,之前思路想错了,直接报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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *