題目:
問那個人可以走完所有的城市的最大承載量是多少
分析：
求最大生成樹的邊的最小值，可以用dijkstra算法變形做，相當(dāng)于把求最小值改為求最大值，
只需把dist初始化為0，并且min處改為max = -1,注意到可能為0，再改動其他地方就行，
詳細(xì)看代碼。。。

設(shè)圖由鄰接矩陣g存儲。
memset(dist,0x3f,sizeof(dist));
memset(used,false,sizeof(used));
dist[0]=0;//設(shè)0為源點
for(i=0;i<n;i++)//循環(huán)n次
{
min=10000000;
for(j=0;j<n;j++)//找到最小值
if(!used[j]&&dist[j]<min)
{
min=dist[j];
k=j;
}
used[k]=true;
for(j=0;j<n;j++)//更新其它點
dist[j]=min(dist[j],dist[k]+g[k][j]);
}

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define X 1002
long int map[X][X],dis[X];
bool use[X];
int main()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
int t,m,n,x,y,z;
int cnt = 1;
cin>>t;
while(t--)
{
memset(map,0,sizeof(map));//初始化為0，因為求的是最大生成樹中的最小值
memset(dis,0,sizeof(dis));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
map[x][y] = map[y][x] = z;
}
memset(use,false,sizeof(use));//標(biāo)記未經(jīng)使用
int k,MAX;
dis[1] = 100000000;//注意此處得標(biāo)記為大于10000000
/dijkstra模板改動一下
for(int i=1;i<=n;i++)
{
MAX = -1; //此處改為最大值
for(int j=1;j<=n;j++)
if(!use[j]&&MAX<dis[j])//改為小于號
MAX = dis[k=j];
use[k] = true;
for(int j=1;j<=n;j++)
if(!use[j]&&dis[j]<min(dis[k],map[k][j]))//改了
dis[j] = min(dis[k],map[k][j]);
}
printf("Scenario #%d:\n",cnt++);
cout<<dis[n]<<endl;
if(t)
cout<<endl;
}
return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/yejinru/archive/2012/02/29/2374684.html

總結(jié)

以上是生活随笔為你收集整理的poj1797Heavy Transportation最大生成树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。