题解 P1396 【营救】

sshwy · 2017-12-05 13:19:32 · 题解

不得不来一发题解

本来看到二分和并查集和图论的标签的时候多害怕的

后来我深思熟虑

其实用最小生成树就行了

首先对边的权值排序

从小到大构建最小生成树

每加一条边就判断s，t的联通

联通了就输出当前联通块的最大权值

因为一旦联通，就说明一定要经过当前的边，即当前的最大权值

类似贪心

其次，构建最小生成树时加入并查集优化

压缩路径

#include<iostream>
#include<algorithm>

using namespace std;

int n,m,s,t;
int f[10001];//father（并查集的内容）
long long total;

struct cs
{
    int x,y,z;
}a[20001];

bool comp(cs a1,cs a2)
{
    return a1.z<a2.z;
}

int gf(int k)//getfather（并查集的内容）
{
    if(f[k]==k)return k;
    f[k]=gf(f[k]);//压缩路径
    return f[k];
}

void un(int b1,int b2)//union（并查集的内容）（联通b1，b2所在的联通块）
{
    int fb1=gf(b1);
    int fb2=gf(b2);
    f[fb1]=fb2;
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a+1,a+m+1,comp);//从小到大

    for(int i=1;i<=n;i++)f[i]=i;//并查集初始化，每个区自成一联通块

    for(int i=1;i<=m;i++)
    {
        if(gf(a[i].x)!=gf(a[i].y))//如果不在同集
        {
            un(a[i].x,a[i].y);
            total=total>a[i].z? total:a[i].z;
        }
        if(gf(s)==gf(t))
        {
            break;
        }
    }
    cout<<total;
    return 0;
}