首页 > 代码库 > 洛谷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);}
洛谷P1396 营救
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。