[poj1797]Heavy Transportation<最大生成树prim&kruskal>

题目链接：http://poj.org/problem?id=1797

题意：给定n个点，m条边，每条边连接两点切有权值。求点1到点n的路径的上的最小边的值最大。。。

翻别人博客找到的题，方法挺多的，直接跑一个最大生成树就行，或者是一个最短路算法也行

我自己用了prim和kruskal 的方法来做

虽然用最短路也可以轻松过，但是我还是选择了生成树

prim

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 #define maxn 1005

 using namespace std;

 struct node{

     int u,v,w,nxt;

 }e[maxn*maxn];

 int n,m,low[maxn],mst[maxn],head[maxn],vis[maxn],ans;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int tot;

 void adde(int u,int v,int w){

     e[tot]=(node){u,v,w,head[u]};

     head[u]=tot++;

 }

 void first(){

     ans=;

     memset(low,,sizeof(low));

     memset(mst,,sizeof(mst));

     memset(head,-,sizeof(head));

     memset(vis,,sizeof(vis));tot=    ;

 }

 void prim(int num){

     int u=,maxx=-ans,maxid;

     for(int i=head[u];i!=-;i=e[i].nxt){

         int v=e[i].v;

         mst[v]=u;low[v]=e[i].w;

     }vis[u]=;

     int nn=n-;

     while(nn--){

         for(int i=;i<=n;i++){

             if(low[i]&&mst[i]){

                 if(low[i]>maxx){

                     maxx=low[i];maxid=i;

                 }

             }

         }

         ans=min(maxx,ans);maxx=;

         low[maxid]=;mst[maxid]=;vis[maxid]=;

         if(maxid==n)break;

         for(int i=head[maxid];i!=-;i=e[i].nxt){

             int v=e[i].v;

             if(e[i].w>low[v]&&!vis[v]){

                 mst[v]=maxid;low[v]=e[i].w;

             }

         }

     }

     printf("Scenario #%d:\n%d\n\n",num,ans);

 }

 int main(){

     int T;T=read();int h=;

     while(T--){

         first();h++;

         n=read();m=read();

         for(int i=;i<=m;i++){

             int u,v,w;

             u=read();v=read();w=read();

             adde(u,v,w);adde(v,u,w);

         }

         prim(h);

     }

 }

kruskal

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 #define maxn 1005

 using namespace std;

 struct node{

     int u,v,w,nxt;

 }e[maxn*maxn];

 int n,m,fa[maxn],sum,ans,vis[maxn];

 int tot;

 void adde(int u,int v,int w){

     e[tot]=(node){u,v,w};

     tot++;

 }

 void first(){

     ans=;sum=;tot=;

     for(int i=;i<=n;i++)fa[i]=i;

 }

 int find(int x){

     if(fa[x]==x)return x;

     return fa[x]=find(fa[x]);

 }

 int comp(const void*a,const void*b){

     return (*(struct node*)a).w<(*(struct node*)b).w?:-;

 }

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 int can(int x,int y){

     int fx=find(x),fy=find(y);

     if(fx!=fy)return ;

     return ;

 }

 int main(){

     int T,k=;T=read();

     while(T--){

         k++;n=read();m=read();

         first();memset(vis,,sizeof(vis));

         for(int i=;i<=m;i++){

             int u=read(),v=read(),w=read();

             adde(u,v,w);adde(v,u,w);

         }e[].w=ans;

         qsort(e+,tot+,sizeof(e[]),comp);

         for(int i=;i<=tot;i++){

             int u=e[i].u,v=e[i].v;

             int fu=find(u),fv=find(v);

             if(fu!=fv){

                 fa[fv]=fu;ans=min(ans,e[i].w);

             }

             if(can(,n)){

                 printf("Scenario #%d:\n%d\n\n",k,ans);break;

             }

         }

     }

 }

PS：注意一下输出的格式，容易错的。

还有就是判断算法的结束条件，并不是当所有的点都加入了，而是当1能到n 的时候就可以跳出了

巴特西

[poj1797]Heavy Transportation<最大生成树prim&kruskal>

最新文章

热门文章