题解 P1396 【营救】

兴安黑熊 · 2018-06-23 09:30:23 · 题解

本题的意思是说：当s到t点联通的时候，最大的边长（权值）是多少？ 当然这里的联通要求路径最短，也就是最小生成树，考虑并查集+克鲁斯卡尔，代码非常好写，好写到超乎你的想象，另外没加ios::sync_with_stdio(false)也没TLE，这不应该，可以看出数据是不卡时间的，代码如下：

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int vis[20001];
struct sa
{
    int a;
    int b;
    int val;
}dp[20001];
int find(int x)
{
    if (x!=vis[x])
    vis[x]=find(vis[x]);
    return vis[x];
}
int join(int x,int y)
{
    int x1=find(x);
    int y1=find(y);
    if (x1!=y1)
      {vis[y1]=x1; return 1;}
   return 0;
}
int cmp(const sa &a,const sa &b)
{
    return a.val<b.val;
}
int main()
{
  int n,m,s,t,num,ans=0;
  cin>>n>>m>>s>>t;
  for(int i=1;i<=n;i++) vis[i]=i;
  for(int i=1;i<=m;i++)
   cin>>dp[i].a>>dp[i].b>>dp[i].val;
   sort(dp+1,dp+m+1,cmp);
   num=0;
   for(int i=1;i<=m;i++)
   {
       if (join(dp[i].a,dp[i].b)==1)
       {ans=max(ans,dp[i].val);
        num++;
       }
       if (num==n-1) break;

       if (find(s)==find(t)) break;
   }
   cout<<ans<<endl;
    return 0;
}