可以做代销的网站都有哪些,网站开发 密码,上海本土互联网公司,网站建设步骤视频教程题目链接
题目链接
题解
要求所有的路径中最小边长的最大值#xff01;
我们贪心的加边#xff0c;依照边从大往小的方式往里添加#xff0c;然后合并并查集。 每次当查询分布在两个待合并的并查集的时候#xff0c;当前的边长就是这次查询的答案。
我们对每个并查集…题目链接
题目链接
题解
要求所有的路径中最小边长的最大值
我们贪心的加边依照边从大往小的方式往里添加然后合并并查集。 每次当查询分布在两个待合并的并查集的时候当前的边长就是这次查询的答案。
我们对每个并查集维护一个集合集合中保存的内容就是一个点在这个并查集中而另一个点不在这个并查集中的询问编号。
当待合并的两个并查集所具有的集合里面拥有相同的询问编号时候回答这个询问编号然后把小的集合向大的集合合并并将回答完的询问编号从集合中移除。
这是一个离线算法。
代码
#include bits/stdc
using namespace std;
int n,m,q;
setint::iterator it;
const int maxm 50005;
const int maxn 11111;
setint Q[11111];
struct edge{int u,v,cost;friend bool operator (edge e1,edge e2){return e1.cost e2.cost;}
}es[maxm];
int ans[maxm];
int parent[maxn];
int find(int x){return x parent[x]?x:parent[x] find(parent[x]);
}
int main(){memset(ans,-1,sizeof(ans));for(int i 1;i maxn;i)parent[i] i;scanf(%d%d,n,m);for(int i 0;i m;i)scanf(%d%d%d,es[i].u,es[i].v,es[i].cost);sort(es,esm);scanf(%d,q);for(int i 0;i q;i){int x,y;scanf(%d%d,x,y);Q[x].insert(i);Q[y].insert(i);}for(int i 0;i m;i){int x es[i].u,y es[i].v,c es[i].cost;int px find(x),py find(y);if(px py) continue;else{if(Q[px].size() Q[py].size())swap(px,py);vectorint tmp;for(it Q[px].begin();it ! Q[px].end();it){int id *it;if(Q[py].count(id)){ans[id] c;tmp.push_back(id);}Q[py].insert(id);}for(int i 0;i tmp.size();i)Q[py].erase(tmp[i]);parent[px] py;}}for(int i 0;i q;i)printf(%d\n,ans[i]);
}
