首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。