php网站开发费用,wordpress加关键词,网站功能模块设计,php网站开发实例教程 源码正题 大意
一个圆形300米的操场#xff0c;外面位置无数排的椅子#xff0c;然后给出一些条件#xff0c;形式为#xff1a; A B x ABx意思为A在B的顺时针方向第x个#xff0c;求有多少个要求无法满足解题思路
用并查集#xff0c;然后一个farfar数组表…正题 大意
一个圆形300米的操场外面位置无数排的椅子然后给出一些条件形式为
A B x ABx
A\ \ \ \ \ \ B\ \ \ \ \ \ x\ \ \ \ \ \ 意思为A在B的顺时针方向第x个求有多少个要求无法满足解题思路
用并查集然后一个farfarfar数组表示离它的fatherfatherfather有多远每次压缩路径。之后如果输入的A和B在一个分量内就进行判断
(far[x]w)%≠far[y](far[x]w)%≠far[y]
(far[x]+w)\%\neq far[y] 这样就累加不满足的条件。 不然就进行连接 (far[x]−far[y]w300)%300(far[x]−far[y]w300)%300
(far[x]-far[y]+w+300)\%300 这样计算连接之后的距离而且防止了负数情况代码
#includecstdio
#includealgorithm
using namespace std;
int n,m,x,y,w,father[50001],far[50001],s;
int find(int x)
{if (father[x]x) {return x;}else{int fafather[x];father[x]find(father[x]);far[x](far[x]far[fa])%300;//压缩路径return father[x];}
}
void unionn(int x,int y,int w)
{int fafind(x),fbfind(y);father[fb]fa;far[fb](far[x]-far[y]w300)%300;//连接两点
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)father[i]i;for (int i1;im;i){scanf(%d%d%d,x,y,w);if (find(x)find(y)){if ((far[x]w)%300!far[y]) s;//统计}elseunionn(x,y,w);//连接}printf(%d,s);
}
