題目大意是，給出一個(gè)無向圖，求兩點(diǎn)間某條路徑上的邊的容量的最大值。可以使用Floyed算法實(shí)現(xiàn)，用d[i][j]表示從第i個(gè)點(diǎn)到第j個(gè)點(diǎn)的全部的路徑上的容量最大值，則d[i][j]=max(d[i][j],min(d[i][k],d[k][j]))。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/2 16:17:25
* File Name: poj2263.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(207);
int T,n,m,cnt,d[kMaxn][kMaxn];
map<string,int> id;
int main()
{
//freopen("data.in","r",stdin);
T=0;
while(scanf("%d%d",&n,&m)==2 && (n || m))
{
cnt=0;
id.clear();
memset(d,0,sizeof(d));
/*
for(int i=0;i<kMaxn;i++)
d[i][i]=kInf;
*/
string a,b;
for(int i=1;i<=m;i++)
{
int w;
cin>>a>>b;
scanf("%d",&w);
if(!id.count(a))
id[a]=++cnt;
if(!id.count(b))
id[b]=++cnt;
d[id[a]][id[b]]=d[id[b]][id[a]]=w;
}
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",d[i][j]);
printf("\n");
}
*/
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=max(d[i][j],min(d[i][k],d[k][j]));
cin>>a>>b;
printf("Scenario #%d\n",++T);
printf("%d tons\n\n",d[id[a]][id[b]]);
}
return 0;
}
posted on 2011-08-02 16:37
lee1r 閱讀(268)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論