参考代码：
（已用堆优化）
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<iterator>
#include<cstdio>
using namespace std;
const int N = 205, M = 40000, oo=0x7fffffff;
struct EdgeT{
int to,wei,next;
}edge[M];
int n,r,en=0,begin,end,head[N],dist[N],a[N],b[N];
map<string,int> m;
bool finished,ok[N];
void AddEdge(int x,int y,int z){//注意是双向
edge[en].to=y;
edge[en].wei=z;
edge[en].next=head[x];
head[x]=en++;
}
void jiaohuan(int &x,int &y){
swap(x,y);
swap(b[x],b[y]);
}
void siftdown(int root,int m){
int child=root*2+1;
while (child<=m){
if (child<m&&dist[a[child+1]]>dist[a[child]]) child++;
if (dist[a[child]]>dist[a[root]]){
jiaohuan(a[child],a[root]);
root=child;
child=root*2+1;
}
else break;
}
}
void siftup(int child){
int parent=(child-1)/2;
while (child){
if (dist[a[child]]>dist[a[parent]]){
jiaohuan(a[child],a[parent]);
child=parent;
parent=(child-1)/2;
}
else break;
}
}
void init(){
cin>>n>>r;
if (n==0&&r==0){
finished=true;
return;
}
finished=false;
fill(head,head+N,-1);
fill(ok,ok+N,false);
en=0;
string c1,c2;
int CityNo=0;
int weight;
for (int i=0;i<r;i++){
cin>>c1>>c2>>weight;
if (m[c1]==0) m[c1]=++CityNo;
if (m[c2]==0) m[c2]=++CityNo;
AddEdge(m[c1],m[c2],weight);
AddEdge(m[c2],m[c1],weight);
}
cin>>c1>>c2;
begin=m[c1];
end=m[c2];
}
bool comp(const int &x,const int &y){ //大顶堆
return dist[x]<dist[y];
}
void solve(){
fill(dist,dist+N,0);
dist[begin]=oo;
ok[begin]=true;
for (int i=head[begin];i!=-1;i=edge[i].next)
dist[edge[i].to]=edge[i].wei;
for (int i=0;i<n;i++) a[i]=i+1;
swap(a[begin-1],a[n-1]);
make_heap(a,a+n-1,comp);
for (int i=0;i<n-1;i++) b[a[i]]=i;
for (int i=n-2;i>=1;i--){
int k=a[0];
ok[k]=true;
if (k==end) return;
jiaohuan(a[0],a[i]);
siftdown(0,i-1);
for (int j=head[k];j!=-1;j=edge[j].next)
if (!ok[edge[j].to]){
dist[edge[j].to]=max(dist[edge[j].to],min(dist[k],edge[j].wei));
siftup(b[edge[j].to]);
}
}
}
int main()
{
int t=0;
while (true){
init();
if (finished) break;
solve();
t++;
if (t>1) printf("\n");
printf("Scenario #%d\n",t);
printf("%d tons\n",dist[end]); //cout<<dist[end]<<endl;
m.clear();
}
return 0;
}posted on 2015-08-29 23:39
龙在江湖 阅读(216)
评论(0) 编辑 收藏 引用 所属分类:
图论