栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 2831 Can We Build This One?

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 2831 Can We Build This One?

#include <cstdio>#include <iostream>#include <algorithm>#define N 1007using namespace std;struct Edge{int u,v,w;int id;int operator<(const Edge e)const{if(w!=e.w) return w<e.w;return id>e.id;}}edge[N<<8];int n,m,q;bool ans[N<<7];struct uset{int p[N];uset(int n){for(int i=1;i<=n;i++)p[i]=i;}int find(int x){return x==p[x]?x:p[x]=find(p[x]);}void merge(Edge e){int u=e.u,v=e.v,id=e.id;int fx=find(u),fy=find(v);if(fx!=fy){if(id) ans[id]=1;else p[fx]=fy;}}};void Kruskal(){sort(edge+1,edge+m+q+1); uset us(n);for(int i=1;i<=m+q;i++) us.merge(edge[i]);}int main(){int k,w;for(;cin>>n>>m>>q;){for(int i=1;i<=m;i++)scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w),edge[i].id=0;for(int i=1;i<=q;i++)scanf("%d%d",&k,&w),edge[m+i]=edge[k],edge[m+i].w=w,edge[m+i].id=i,ans[i]=0;Kruskal();for(int i=1;i<=q;i++)puts(ans[i]?"Yes":"No");}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/372825.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号