首页 > 代码库 > POJ 2831

POJ 2831

次小生成树。求出两点间最短路径的最大权值,再把要加入的边与之比较即可。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 const int MAXN=1010; 8 const int MAXM=100010; 9 const int inf=100000000;10 int map[MAXN][MAXN];11 int edge[MAXM][3];12 bool exist[MAXN][MAXN],used[MAXN][MAXN],vis[MAXN];13 int f[MAXN][MAXN],dist[MAXN],pre[MAXN]; 14 int m,n,q;15 int ans1=0;16 void init(){17     for(int i=1;i<=n;i++){18         vis[i]=false;19         for(int j=i;j<=n;j++){20             map[i][j]=map[j][i]=inf;21             exist[i][j]=exist[j][i]=used[i][j]=used[j][i]=false;22             f[i][j]=f[j][i]=0;23         }24     }25 }26 27 void prim(){28     dist[1]=0;29     for(int i=2;i<=n;i++){30         dist[i]=map[1][i];31         if(dist[i]!=inf)32         pre[i]=1;33         else pre[i]=-1;34     }35     vis[1]=true;36     for(int i=1;i<=n;i++){37         int min=inf,p=-1;38         for(int k=1;k<=n;k++){39             if(dist[k]<min&&!vis[k]){40                 min=dist[k]; p=k;41             }42         }43         if(p==-1) return ;44         for(int k=1;k<=n;k++){45             if(vis[k]){46                 f[k][p]=max(f[k][pre[p]],map[pre[p]][p]);47                 f[p][k]=f[k][p];                48             }49         }50         vis[p]=true;51         for(int k=1;k<=n;k++){52             if(!vis[k]&&map[p][k]<dist[k]){53                 dist[k]=map[p][k];54                 pre[k]=p;55             }56         }57     }58 }59 60 int main(){61     int u,v,d;62     int c,w;63     while(scanf("%d%d%d",&n,&m,&q)!=EOF){64         init();65         for(int i=1;i<=m;i++){66             scanf("%d%d%d",&u,&v,&d);67             edge[i][0]=u; edge[i][1]=v; edge[i][2]=d;68             if(d<map[u][v])69             map[u][v]=map[v][u]=d;70         }71         prim();72         for(int i=1;i<=q;i++){73             scanf("%d%d",&c,&w);74             u=edge[c][0]; v=edge[c][1];75             if(w<=f[u][v])76             printf("Yes\n");77             else printf("No\n");78         }79     }80     return 0;81 }
View Code