首页 > 代码库 > 洛谷P1396 营救

洛谷P1396 营救

P1396 营救

题目描述

“咚咚咚……”“查水表!”原来是查水表来了,现在哪里找这么热心上门的查表员啊!小明感动的热泪盈眶,开起了门……

妈妈下班回家,街坊邻居说小明被一群陌生人强行押上了警车!妈妈丰富的经验告诉她小明被带到了t区,而自己在s区。

该市有m条大道连接n个区,一条大道将两个区相连接,每个大道有一个拥挤度。小明的妈妈虽然很着急,但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从s至t的路线,使得经过道路的拥挤度最大值最小。

输入输出格式

输入格式:

 

第一行四个数字n,m,s,t。

接下来m行,每行三个数字,分别表示两个区和拥挤度。

(有可能两个区之间有多条大道相连。)

 

输出格式:

 

输出题目要求的拥挤度。

 

输入输出样例

输入样例#1:
3 3 1 3							1 2 22 3 11 3 3
输出样例#1:
2

说明

数据范围

30% n<=10

60% n<=100

100% n<=10000,m<=2n,拥挤度<=10000

题目保证1<=s,t<=n且s<>t,保证可以从s区出发到t区。

样例解释:

小明的妈妈要从1号点去3号点,最优路线为1->2->3。

两种做法:

1.克鲁斯卡尔,生成树

2.二分答案+spfa

技术分享
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define maxn 10010struct node{    int from,to,v;}e[maxn*4];int n,m,s,t,fa[maxn];int cmp(node x,node y){return x.v<y.v;}int find(int x){    if(fa[x]==x)return fa[x];    else return fa[x]=find(fa[x]);}int main(){    scanf("%d%d%d%d",&n,&m,&s,&t);    int x,y,z;    for(int i=1;i<=m;i++){        scanf("%d%d%d",&x,&y,&z);        e[i].from=x;e[i].to=y;e[i].v=z;    }    sort(e+1,e+m+1,cmp);    for(int i=1;i<=n;i++)fa[i]=i;    for(int i=1;i<=m;i++){        int f1=find(e[i].from),f2=find(e[i].to);        int ans=0;        if(f1!=f2){            fa[f1]=f2;            ans=e[i].v;        }        f1=find(s);f2=find(t);        if(f1==f2){            printf("%d",ans);            return 0;        }    }}
克鲁斯卡尔
技术分享
#include<iostream>#include<cstdio>#include<queue>#include<cstring>using namespace std;#define maxn 10010int n,m,s,t,num,head[maxn*2],ans,dis[maxn];struct node{    int to,pre,v;}e[maxn*4];bool vis[maxn];void Insert(int from,int to,int v){    e[++num].to=to;    e[num].v=v;    e[num].pre=head[from];    head[from]=num;}bool check(int x){    memset(vis,0,sizeof(vis));    memset(dis,0x3f3f3f3f,sizeof(dis));    queue<int>q;    while(!q.empty())q.pop();    q.push(s);    dis[s]=0;vis[s]=1;    while(!q.empty()){        int cur=q.front();q.pop();vis[cur]=0;        for(int i=head[cur];i;i=e[i].pre){            int to=e[i].to;            if(e[i].v<dis[to]){                dis[to]=e[i].v;                if(!vis[to]&&dis[to]<=x){                    q.push(to);                    vis[to]=1;                }            }        }    }    if(dis[t]>x)return 0;    else return 1;}int main(){    scanf("%d%d%d%d",&n,&m,&s,&t);    int x,y,z;    int l=0x7fffffff,r=0;    for(int i=1;i<=m;i++){        scanf("%d%d%d",&x,&y,&z);        Insert(x,y,z);        Insert(y,x,z);        r=max(r,z);        l=min(l,z);    }    while(l<=r){        int mid=(l+r)>>1;        if(check(mid))ans=mid,r=mid-1;        else l=mid+1;    }    printf("%d",ans);}
二分答案+spfa

洛谷P1396 营救