题目链接：http://poj.org/problem?id=1797
题意：给定n个点，m条边，每条边连接两点切有权值。求点1到点n的路径的上的最小边的值最大。。。
翻别人博客找到的题，方法挺多的，直接跑一个最大生成树就行，或者是一个最短路算法也行
我自己用了prim和kruskal 的方法来做
虽然用最短路也可以轻松过，但是我还是选择了生成树
prim
1 #include<cstdio>
2 #include<cmath>
3 #include<algorithm>
4 #include<iostream>
5 #include<cstdlib>
6 #include<cstring>
7 #include<queue>
8 #define maxn 1005
9 using namespace std;
10 struct node{
11 int u,v,w,nxt;
12 }e[maxn*maxn];
13
14 int n,m,low[maxn],mst[maxn],head[maxn],vis[maxn],ans;
15
16 int read(){
17 int x=0,f=1;char ch=getchar();
18 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
19 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
20 return x*f;
21 }
22
23 int tot;
24 void adde(int u,int v,int w){
25 e[tot]=(node){u,v,w,head[u]};
26 head[u]=tot++;
27 }
28
29 void first(){
30 ans=1000000001;
31 memset(low,0,sizeof(low));
32 memset(mst,0,sizeof(mst));
33 memset(head,-1,sizeof(head));
34 memset(vis,0,sizeof(vis));tot=0 ;
35 }
36
37 void prim(int num){
38 int u=1,maxx=-ans,maxid;
39 for(int i=head[u];i!=-1;i=e[i].nxt){
40 int v=e[i].v;
41 mst[v]=u;low[v]=e[i].w;
42 }vis[u]=1;
43 int nn=n-1;
44 while(nn--){
45 for(int i=1;i<=n;i++){
46 if(low[i]&&mst[i]){
47 if(low[i]>maxx){
48 maxx=low[i];maxid=i;
49 }
50 }
51 }
52 ans=min(maxx,ans);maxx=0;
53 low[maxid]=0;mst[maxid]=0;vis[maxid]=1;
54 if(maxid==n)break;
55 for(int i=head[maxid];i!=-1;i=e[i].nxt){
56 int v=e[i].v;
57 if(e[i].w>low[v]&&!vis[v]){
58 mst[v]=maxid;low[v]=e[i].w;
59 }
60 }
61 }
62 printf("Scenario #%d:
%d
",num,ans);
63 }
64
65 int main(){
66 int T;T=read();int h=0;
67 while(T--){
68 first();h++;
69 n=read();m=read();
70 for(int i=1;i<=m;i++){
71 int u,v,w;
72 u=read();v=read();w=read();
73 adde(u,v,w);adde(v,u,w);
74 }
75 prim(h);
76 }
77 }
kruskal
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<cstdlib>
6 #include<cmath>
7 #include<queue>
8 #define maxn 1005
9 using namespace std;
10
11 struct node{
12 int u,v,w,nxt;
13 }e[maxn*maxn];
14
15 int n,m,fa[maxn],sum,ans,vis[maxn];
16
17 int tot;
18 void adde(int u,int v,int w){
19 e[tot]=(node){u,v,w};
20 tot++;
21 }
22
23 void first(){
24 ans=1000000001;sum=0;tot=0;
25 for(int i=1;i<=n;i++)fa[i]=i;
26 }
27
28 int find(int x){
29 if(fa[x]==x)return x;
30 return fa[x]=find(fa[x]);
31 }
32
33 int comp(const void*a,const void*b){
34 return (*(struct node*)a).w<(*(struct node*)b).w?1:-1;
35 }
36
37 int read(){
38 int xx=0,ff=1;char ch=getchar();
39 while(ch<'0'||ch>'9'){if(ch=='-')ff=-1;ch=getchar();}
40 while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
41 return xx*ff;
42 }
43
44 int can(int x,int y){
45 int fx=find(x),fy=find(y);
46 if(fx!=fy)return 0;
47 return 1;
48 }
49
50 int main(){
51 int T,k=0;T=read();
52 while(T--){
53 k++;n=read();m=read();
54 first();memset(vis,0,sizeof(vis));
55 for(int i=1;i<=m;i++){
56 int u=read(),v=read(),w=read();
57 adde(u,v,w);adde(v,u,w);
58 }e[0].w=ans;
59 qsort(e+1,tot+1,sizeof(e[0]),comp);
60 for(int i=1;i<=tot;i++){
61 int u=e[i].u,v=e[i].v;
62 int fu=find(u),fv=find(v);
63 if(fu!=fv){
64 fa[fv]=fu;ans=min(ans,e[i].w);
65 }
66 if(can(1,n)){
67 printf("Scenario #%d:
%d
",k,ans);break;
68 }
69 }
70 }
71 }
PS：注意一下输出的格式，容易错的。
还有就是判断算法的结束条件，并不是当所有的点都加入了，而是当1能到n 的时候就可以跳出了