hdu 3047 Zjnu Stadium
2024-09-21 19:45:49
http://acm.hdu.edu.cn/showproblem.php?pid=3047
带权并差集
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 60000
using namespace std; int f[maxn],d[maxn];
int ans=;
int n,m; int find1(int x)
{
if(x==f[x]) return x;
int f1=f[x];
f[x]=find1(f[x]);
d[x]+=d[f1];
return f[x];
} void union1(int a,int b,int x)
{
int fa=find1(a);
int fb=find1(b);
if(fa!=fb)
{
f[fb]=fa;
d[fb]=d[a]+x-d[b];
return;
}
if(fa==fb)
{
if(d[b]-d[a]!=x) ans++;
}
} void inti()
{
for(int i=; i<=n; i++)
{
f[i]=i;
}
memset(d,,sizeof(d));
ans=;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
inti();
int a1,b1,x1;
for(int i=; i<=m; i++)
{
scanf("%d%d%d",&a1,&b1,&x1);
union1(a1,b1,x1);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- js窗口边缘滑入滑出效果-初级代码
- 模板短信接口调用java,pythoy版(一) 网易云信
- php中的curl】php中curl的详细解说
- 隐藏NavigationBar 带来的坑
- printf 格式化最常用用法
- ruby和Python简单对比
- CDOJ 1270 Playfair(模拟)
- URL的# (转)
- Entity Framework+SQLite+DataBaseFirst
- oozie note
- was cached in the local repository, resolution will not be reattempted until the update interval of fintech has elapsed or updates are forced
- Spring Ioc工作机制 初步
- Docker 安装 MySQL
- MySQL查询优化注意下面的四个细节
- tf.pad(one_hot_encoding, [[0, 0], [1, 0]], mode=&#39;CONSTANT&#39;)
- gitlab的md文件内使用锚点
- SCP报错:WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
- QT学习笔记6:常见的 QGraphicsItem
- Windows下遍历某目录下的文件
- 2、Web基本介绍及Html语法介绍