题解 P1396 【营救】

以梦为马 · 2018-07-12 22:26:42 · 题解

这道题所要求的是“经过道路的拥挤度最大值的最小值”，换句话说，也就是让从s到达t的所有路径中的最大权值最小，并求出这个最小值。听起来很拗口(°:з」∠) 由这个题干，不难想到：Kruskal算法求MST的贪心策略可以一用。为了得到题干中要求的“最小值”，我们总是选择剩下的边中权值最小的边相连两个节点（用并查集判断以避免成环）。题干中要求研究的是从s到t的路径，虽然一些加入的边并不属于所要求的路径，但是恰好使得s和t连通的那条边，一定是s到t的路径中的最大值。而在Kruskal算法的贪心策略前提下，这个最大值一定是题干所要求的“最小值”。 总而言之，这一解法是基于稍加改动的Kruskal算法。 Kruskal算法求MST的核心有两个：一是边的排序，二是并查集的判是否成环。边的排序我选择用结构体储存起点，终点，权值，并用stl的qsort()函数排序。 下面贴上AC代码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define maxn 10005
#define maxm 20005
using namespace std;
struct node
{
  int s,t,w;     
};
struct node g[maxm];
int n,m,s,t,fa[maxn];
int cmp(const void *a,const void *b)
{
  struct node *p=(struct node *)a,*q=(struct node *)b;
  return p->w-q->w;  
} 
void init()
{
  int u,v,w;
  scanf("%d%d%d%d",&n,&m,&s,&t);
  for(int i=1;i<=n;i++)fa[i]=i;
  for(int i=0;i<m;i++)
  {
    scanf("%d%d%d",&u,&v,&w);
    g[i].s=u;g[i].t=v;g[i].w=w;        
  }     
  qsort(g,m,sizeof(g[0]),cmp);
}
int find(int x)
{
  return fa[x]==x?x:fa[x]=find(fa[x]);  
}
void merge(int s,int t)
{
  fa[find(s)]=find(t);     
}
int main()
{
  int s1,t1;
  init();
  for(int i=0;i<m;i++)
  {
    s1=g[i].s;t1=g[i].t;
    if(find(s1)!=find(t1))
      merge(s1,t1);        
    if(find(s)==find(t)) 
    { 
      printf("%d\n",g[i].w);
      break; 
    }
  }
  return 0;  
}