题目：uva 10099 The Tourist Guide
题意：给出一个无向图，每条路有一个容量。
从 s 到 t 的一条最大的流量。
分析：这个题目能够用最短路的算法来做。最短路是求从 s 到 t 的最短路，这里是求从 s 到 t 的最小容量。最短路的三种算法都能够。
nyoj的使我们比赛的题目，有坑，图有重边。要处理，还有s可能等于t。
spfa代码：
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;
const int N = 120;
const int inf = 0x3f3f3f3f;
struct Node
{
int v,len;
};
vector<Node> v[N];
void add_Node(int x,int y,int z)
{
v[x].push_back((Node){y,z});
v[y].push_back((Node){x,z});
}
void v_clear(int n)
{
for(int i=1;i<=n;i++)
v[i].clear();
}
int dis[N];
void spfa(int s)
{
memset(dis,inf,sizeof(dis));
queue<int> q;
q.push(s);
while(!q.empty())
{
int tmp=q.front();
q.pop();
for(int i=0;i<v[tmp].size();i++)
{
Node ff=v[tmp][i];
int ans=min(dis[tmp],ff.len);
//printf("--%d %d
",ff.v,ans);
if(dis[ff.v]!=inf){
if(ans>dis[ff.v]) //注意仅仅要更新了都要压入
q.push(ff.v);
dis[ff.v]=max(dis[ff.v],ans);
}
else
q.push(ff.v),
dis[ff.v]=ans;
}
}
}
int main()
{
int n,m,cas=1;
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0)
break;
for(int i=0; i<m; ++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add_Node(a,b,c);
}
int s,t,num;
scanf("%d%d%d",&s,&t,&num);
spfa(s);
//printf("%d
",dis[t]);
if(dis[t]>=inf)
printf("-1
");
else{
dis[t]--;
printf("Scenario #%d
",cas++);
printf("Minimum Number of Trips = %d
",(num+dis[t]-1)/dis[t]);}
v_clear(n);
}
return 0;
}
nyoj floyd 代码：
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;
const int N = 120;
const int inf = 0x3f3f3f3f;
int mp[N][N];
int main()
{
int n,m,cas=1;
while(~scanf("%d%d",&n,&m))
{
memset(mp,inf,sizeof(mp));
for(int i=1;i<=n;i++)
mp[i][i]=0;
for(int i=0; i<m; ++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(mp[a][b]!=inf)
mp[a][b]=mp[b][a]=max(mp[a][b],c);
else
mp[a][b]=mp[b][a]=c;
}
int s,t,num;
scanf("%d%d%d",&s,&t,&num);
for(int k=1; k<=n; ++k) //floyd
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
int tmp = min(mp[i][k], mp[k][j]);
if(mp[i][j]==inf) mp[i][j] = tmp;
else mp[i][j] = max(mp[i][j],tmp);
}
}
if(s==t)
puts("0");
else if(mp[s][t]>=inf)
printf("-1
");
else{
mp[s][t]--;
printf("%d
",(num+mp[s][t]-1)/mp[s][t]);}
}
return 0;
}
nyoj dij代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 120;
const int inf = 0x3f3f3f3f;
int map[N][N];
int n,m;
int dij(int s,int t)
{
int vis[N],dis[N];
memset(vis,0,sizeof(vis));
memset(dis,-1,sizeof(dis));
dis[s]=inf;
//vis[t]=1;
int tmp=s;
while(1)
{
vis[tmp]=1;
for(int i=1;i<=n;i++)
{
if(map[tmp][i]>0)
{
if(map[tmp][i]>dis[i])
{
dis[i]=min(dis[tmp],map[tmp][i]);
}
}
}
int max=-1;
for(int i=1;i<=n;i++)
{
if(vis[i]==0 && dis[i]>max)
{
max=dis[i];
tmp=i;
}
}
// printf("--%d
",tmp);
if(max==-1)
return dis[t];
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(map,0,sizeof(map));
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
map[x][y]=max(map[x][y],z);
map[y][x]=map[x][y];
}
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int flow=dij(x,y);
// printf("%d
",flow);
if(x==y)
{
printf("0
");continue;
}
if(flow==-1)
{
printf("-1
");continue;
}
int ans=(z-2)/(flow-1)+1; ///ans=(z-1)/(flow-1);
// if((z-1)%(flow-1)!=0 && (z-1)%(flow-1)!=1)
// ans++;
printf("%d
",ans);
}
return 0;
}