首页 > 代码库 > uva Fire Station(FLODY+枚举)(挺不错的简单题)
uva Fire Station(FLODY+枚举)(挺不错的简单题)
消防站
题目链接:Click Here~
题意分析:
就是给你f个消防站,n个路口。要你求出在已有消防站的基础上在n个路口的哪个路口上在建立一个消防站,使得n个路口的到离自己最近的消防站最近的距离中最大的一个值最小。即:求n个最近路口中最大的一个,使其改最大值最小。详细的要求自己看题目吧~
算法分析:
因为,是n个路口到每个消防站的距离。所以,我们可以想到先用一次Flody算法。把每两点的最近距离给算出来。之后在枚举N个路口,进行判断比较得出答案。
#include <iostream> #include <algorithm> #include <sstream> #include <vector> #include <cstdio> #include <cstring> using namespace std; const int INF = ~0U >> 2; const int MAXN = 500+10; int G[MAXN][MAXN],fire[MAXN]; void Flody(int n) { for(int k = 1;k <= n;++k) for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) if(G[i][k] != INF&&G[k][j] != INF) G[i][j] = min(G[i][j],G[i][k]+G[k][j]); } int main() { int T,f,n; cin>>T; while(T--) { int x; scanf("%d%d",&f,&n); memset(fire,0,sizeof(fire)); for(int i = 0;i < f;++i){ cin>>x; fire[x] = 1; } cin.ignore(); string line; int u,v,w; istringstream iss; for(int i = 0;i <= n;++i) for(int j = 0;j <= n;++j) G[i][j] = (i==j?0:INF); while(getline(cin,line),line.length()>0){ iss.clear(); iss.str(line); iss>>u>>v>>w; G[u][v] = G[v][u] = w; } Flody(n); int minrode = INF,ans = 1; int maxrode,shortest; for(int i = 1;i <= n;++i){ /*//在第i个路口建消防站的结果*/ maxrode = 0; for(int j = 1;j <= n;++j){ /*//在第i个路口建消防站后的最长距离*/ shortest = INF; for(int k = 1;k <= n;++k){ if(!fire[k]&&k != i)continue; /*//即不是已有的消防站也不是要建立的消防站路口*/ shortest = min(shortest,G[j][k]); } maxrode = max(maxrode,shortest); } if(maxrode < minrode){ minrode = maxrode; ans = i; } } cout<<ans<<endl; if(T)cout<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。