题解 P1396 【营救】

「QQ红包」 · 2016-02-15 16:12:35 · 题解

最开始以为是最短路径，但是发现拥挤度跟最短路并无卵关系。

这道题是最小生成树， prim和克鲁斯卡尔任意。

我用的是克鲁斯卡尔。

克鲁斯卡尔的话只要起点和终点在一个集合了，就输出最后进入集合的那条边的边权值。毕竟之前从小到大排序过了来着。

/*
第一行四个数字n，m，s，t。
接下来m行，每行三个数字，分别表示两个区和拥挤度。
（有可能两个区之间有多条大道相连。)
输出格式：
输出题目要求的拥挤度。
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm> //一堆没用的头文件 
#define LL unsigned long long 
using namespace std; 
int n,m,s,t,i;
struct hhh
{
    int u,v,c;
}a[100000];
int f[20000];
int cmp(const hhh &a,const hhh &b)
{
    if(a.c<b.c) return 1;
        else return 0;
}
int gf(int x)//并查集找爸爸 
{
    if (f[x]==x) return x; else//如果爸爸是本身就返回自己 
    {
        return f[x]=gf(f[x]);//返回祖宗 
    }
}
void un(int x,int y)//合并 
{
    int xx=gf(x);//找x的祖宗 
    int yy=gf(y);//找y的祖宗 
    if (xx!=yy)//如果祖宗不同 
    {
        f[xx]=yy;//合并祖宗 
    }
    return;
}  
int main()
{
    scanf("%d %d %d %d",&n,&m,&s,&t);//n为城市数，m为边数，s为起点，t为终点
    for (i=1;i<=m;i++)
        scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].c);
    sort(a+1,a+m+1,cmp);//边权值从小到大排序 
    int haha=0;int sum=0;
    for (i=1;i<=n;i++)//f数组初始化
    {
        f[i]=i;
    }
    for (i=1;i<=m&&haha<=n-1;i++)
    {
        if (gf(a[i].u)!=gf(a[i].v))//判断是否在集合内 
        {
            un(a[i].u,a[i].v);//合并 
            haha++;//每次将两个不同集合中的点合并，都将使haha值减1 
        }
        if (gf(s)==gf(t))//起点和终点在同一个集合。
        {
            cout<<a[i].c;
            return 0;
        }
    }
    return 0;
}