poj 1797

• 和POJ2253 思路反过来,数据太大, tle
• 求 每个通路中桥梁最小值的集合中的最大值

  #include <iostream>
  #include <string.h>
  #include <math.h>
  
  using namespace std;
  
  const int maxn = 1001;
  
  int e[maxn][maxn];
  int n,m;
  int cnt;
  
  void floyd() {
  	for (int k=1; k<=n; k++)  // k点作为 中转点
  		for (int i=1; i<=n; i++)
  			for (int j=1; j<=n; j++) // e[i][j] 保存的就是i到j中 每个通路中 的 最大桥梁值中 的 最小桥梁值 
  				// 先通过floyd找到 最大桥梁值, min()来更新其中 最小的值. 
  				e[i][j] = max(e[i][j],min(e[i][k],e[k][j])); 
  			
  	printf("Scenario #%d\n",++cnt);
  	printf("%d\n\n",e[1][2]);
  }
  void read() {
  	int a,b,c;
  	cin >> n >> m; // n个点,m条边
  	for (int i=1; i<=m; i++) {
  		cin >> a >> b >> c;
  		e[a][b] = e[b][a] = c;
  	}
  }
  void init() {
  	memset(e,0x3f,sizeof e);
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	int times;
  	cin >> times;
  	while (times--) {
  		init();
  		read();
  		floyd();
  	}
  	return 0;
  }

• dist[i]代表源点到点i所有通路上桥梁最小的最大值,
• 遍历所有的点,先找到每个点附近的最远的点,记录这个最远点,然后遍历仍未访问过的点通过它们来更新dist[最远点]
• dist[j] = max(dist[j],min(dist[k],e[k][j]))中,
  min(dist[k],e[k][j])表示能通过这条路的最小质量,
  max(dist[j],min())表示达到j点所有通路最小值中的最大值

  #include <iostream>
  #include <algorithm>
  #include <string.h>
  
  using namespace std;
  
  const int maxn = 1001;
  const int inf = 0x3f3f3f3f;
  int n,m;
  int e[maxn][maxn];
  bool vis[maxn];
  int dist[maxn];
  int cnt;
  void read() {
  	memset(e,0,sizeof e);
  	memset(dist,inf,sizeof dist);
  	scanf("%d%d",&n,&m);
  	for (int i=1; i<=m; i++) {
  		int u,v,w;
  		scanf("%d%d%d",&u,&v,&w);
  		e[u][v] = e[v][u] = w; //双向图
  	}
  }
  void dij() {
  	// 初始化标记数组为0,这一步while多次
  	memset(vis,0,sizeof vis); 
  	// 从根节点出发、
  	vis[1] = 1;
  	dist[1] = 0;
  	for (int i=1; i<=n; i++) dist[i] = e[1][i]; //初始化源点到所有点的路径值
  	for (int i=1; i<=n; i++) { //遍历所有的点,更新每一个点到源点的路径
  		int mindis = -1;
  		int to = -1;
  		for (int j=1; j<=n; j++) { 
  			if (!vis[j] && dist[j]>mindis) { //没有去过,且距离源点最大的点
  				mindis = dist[j];
  				to = j;
  			}
  		}
  		if (to == -1) break;
  		vis[to] = 1;
  		for (int j=1; j<=n; j++) 
  			if (!vis[j]) 
  				dis[j] = max(dis[j],min(dis[k],e[k][j]));
  	}
  }
  void print() {
  	printf("Scenario #%d:%d\n",++cnt,dist[n]);
  }
  int main() {
  	int times;
  	scanf("%d",&times);
  	wile (times--) {
  		read(); 
  		dij();
  		print();
  	}
  	return 0;
  }