poj 1797Heavy TransportationDijkstra&&Kruskal

Background  Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.  Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.  Problem  You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo's place) to crossing n (the customer's place). You may assume that there is at least one path. All streets can be travelled in both directions. Input The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings. Output The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line. Sample Input 1 3 3 1 2 3 1 3 4 2 3 5 Sample Output Scenario #1: 4

题意概括：有n路口，m条路，每条路都有其能承载的最大值，意思就是说如果超过这个最大值就算超重就不能在这条路上走，需要找出一条路径，这条路径在所有路径中拥有最大的承载量。一条路径的最大承载量是这条路径里面所有路的最小承载量，因为肯定要经过这个最小承载量所在的路，如果大于他就是超重了。如样例，可以找出两条路径 1—2—3 里面的承载量分别是3，5，而这条路径的最大承载量就是3，大于3，1到2就无法行走；另一条是1—3承载量是4，所以最后找出的最大承载量是4。

解题思路：开始是按照Dijkstra写的，但是后来发现用Kruskal更简单。

代码1：Dijkstra

#include<stdio.h> #include<string.h> #define N 1100 #define INF 0x3f3f3f int map[N][N]; int d[N]; int visit[N]; int n; int min(int a,int b) { if(a>b) a=b; return a; } void Dijkstra(int x) { memset(visit,0,sizeof(visit)); int i,j; for(i=1;i<=n;i++) { d[i]=map[x][i]; } for(i=1;i<=n;i++) { int min_cost = -1; int index; for(j=1;j<=n;j++) { if(visit[j]==0&&d[j]>min_cost) { min_cost=d[j]; // printf("%d\n",d[j]); index=j; } } visit[index]=1; // printf("%d\n\n\n",index); for(j=1;j<=n;j++) { if(visit[j]==0&&d[j]<min(map[index][j],min_cost)) { d[j]=min(map[index][j],min_cost); } } } printf("%d\n\n",d[n]); } int main() { int i,j,m,k,l,u,v,w; int T,t=0; scanf("%d",&T); while(T--) { t++; scanf("%d%d",&n,&m); memset(map,0,sizeof(map)); for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); map[u][v]=map[v][u]=w; } printf("Scenario #%d:\n",t); Dijkstra(1); } return 0; }代码2：Kruskal

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define M 1100000 #define N 110000 struct edge { int u,v,w; }e[M]; int i,j,m,n; int f[N]; int min(int a,int b) { if(a>b) a=b; return a; } bool cmp(edge a,edge b) { return a.w>b.w; } int getf(int u) { if(f[u]==u) { return u; } else { f[u]=getf(f[u]); return f[u]; } } int merge (int u,int v) { int t1=getf(u); int t2=getf(v); if(t1!=t2) { f[t2]=t1; return 1; } return 0; } void Kruskal() { int num=0,sum=99999999; for(i=1;i<=n;i++) { f[i]=i; } for(i=0;i<m;i++) { if(merge(e[i].u,e[i].v)) { sum=min(sum,e[i].w); if(getf(1)==getf(n)) { break; } } } printf("%d\n\n",sum); } int main() { int t=0,T; scanf("%d",&T); while(T--) { t++; scanf("%d%d",&n,&m); for(i=0;i<m;i++) { scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); } sort(e,e+m,cmp); printf("Scenario #%d:\n",t); Kruskal(); } return 0; }