POJ1797Heavy Transportation 最短路变形

56 阅读 0 评论 37 点赞

我是靠谱客的博主顺利路人，最近开发中收集的这篇文章主要介绍POJ1797Heavy Transportation 最短路变形，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：点击打开链接

题意：

给定n个顶点，以及m条边的描述，每条边的描述包括：起点、终点、权重。现在要从顶点1出发到达顶点n，求路径中能够承受的最大权重。

其实就是求1-N的最大路径的最小值。

分析：令dist[i]表示从顶点1到顶点i的可行路径中各边权值的最大值的最小值。

因为是求最大距离的最小值，dist初始化时要和原来的相反，即dist初始化为0。

这里给出kruskal和spfa两种方法。。

spfa

/*求最大路径的最小值*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<cstdio>
const int INF=1<<30;
typedef long long LL;
using namespace std;
const int maxn=10015;
struct Edge
{
int e,w;
Edge(){}
Edge(int _e,int _w):e(_e),w(_w){}
};
int dist[maxn];
vector<Edge> G[maxn];
int T,N,M;
void spfa(int v)
{
memset(dist,0,sizeof(dist)); //和以前的相反
queue<int> q;
dist[v]=INF;
q.push(v);
while(!q.empty())
{
int s=q.front();q.pop();
for(int i=0;i<G[s].size();i++)
{
int e=G[s][i].e;
if(min(dist[s],G[s][i].w)>dist[e]) //若能拓展
{
dist[e]=min(dist[s],G[s][i].w);
q.push(e);
}
}
}
}
int main()
{
//	freopen("E:\ACM\test.txt","r",stdin);
cin>>T;
for(int t=1;t<=T;t++)
{
cin>>N>>M;
int s,e,w;
for(int i=0;i<maxn;i++) G[i].clear();
for(int i=0;i<M;i++)
{
cin>>s>>e>>w;
G[s].push_back(Edge(e,w));
G[e].push_back(Edge(s,w));
}
spfa(1);
printf("Scenario #%d:n%dn",t,dist[N]);
if(t!=T) puts("");
}
return 0;
}

利用Kruskal的思想，把每段道路的权值按照从大到小排序，然后依次加边直至 1 可达 n为止，此时这条路中权值即为答案。(最大生成树的最小值)

/*求最大生成树的最小值*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<cstdio>
const int INF=1<<30;
typedef long long LL;
using namespace std;
const int maxn=20015;
struct Edge
{
int s,e,w; //起点，终点，权值
Edge(){}
Edge(int _s,int _e,int _w):s(_s),e(_e),w(_w){}
bool operator <(const Edge &v)const{
return w>v.w;
}
};
vector<Edge> edges;
vector<int> par;
int T,N,M;
int GetRoot(int a)
{
return par[a]==a?a:par[a]=GetRoot(par[a]);
}
void Merge(int a,int b)
{
int p1=GetRoot(a);
int p2=GetRoot(b);
if(p1==p2) return;
par[p2]=p1;
}
int main()
{
//	freopen("E:\ACM\test.txt","r",stdin);
cin>>T;
for(int t=1;t<=T;t++)
{
cin>>N>>M;
int s,e,w;
edges.clear();par.clear();
for(int i=0;i<=N;i++) par.push_back(i);
for(int i=0;i<M;i++)
{
cin>>s>>e>>w;
edges.push_back(Edge(s,e,w));
edges.push_back(Edge(e,s,w));
}
sort(edges.begin(),edges.end()); //边权值按大到小排序
int ans=INF;
for(int i=0;i<edges.size();i++)
{
Merge(edges[i].s,edges[i].e);
if(GetRoot(1)==GetRoot(N))
{
ans=edges[i].w;break;
}
}
printf("Scenario #%d:n%dn",t,ans);
if(t!=T) puts("");
}
return 0;
}