题目链接：http://poj.org/problem?id=1797
题意：给定n个点，m条边，每条边连接两点切有权值。求点1到点n的路径的上的最小边的值最大。。。
翻别人博客找到的题，方法挺多的，直接跑一个最大生成树就行，或者是一个最短路算法也行
我自己用了prim和kruskal 的方法来做
虽然用最短路也可以轻松过，但是我还是选择了生成树
prim
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 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:\n%d\n\n",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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 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:\n%d\n\n",k,ans);break;68 }69 }70 }71 }
PS：注意一下输出的格式，容易错的。
还有就是判断算法的结束条件，并不是当所有的点都加入了，而是当1能到n 的时候就可以跳出了