HDU-3038-How Many Answers Are Wrong

链接：https://vjudge.net/problem/HDU-3038#author=0

题意：

给出N和M

有M次记录，以l,r,v给出，表示l-r区间和为v问，有多少是错误的答案。

思路：

带权并查集。

sum[i] 表示i到F[i]的和。

代码：

#include <iostream> #include <memory.h> #include <string> #include <istream> #include <sstream> #include <vector> #include <stack> #include <algorithm> #include <map> #include <queue> #include <math.h> using namespace std; const int MAXN = 500086; int Father[MAXN]; int Sum[MAXN];int Get_F(int x) {if (x == Father[x])return x;int tmp = Father[x];Father[x] = Get_F(Father[x]);Sum[x] += Sum[tmp];return Father[x]; }int main() {int n,m;//while (scanf("%d%d",&n,&m))while (cin >> n >> m){for (int i = 0; i <= n; i++)Father[i] = i;memset(Sum, 0, sizeof(Sum));int l, r, v;int cnt = 0;for (int i = 1; i <= m; i++){scanf("%d%d%d", &l, &r, &v);l--;int tl = Get_F(l);int tr = Get_F(r);if (tl != tr){Father[tl] = tr;Sum[tl] = Sum[r] + v - Sum[l];}else{if (Sum[l] - Sum[r] != v)cnt++;}}printf("%d\n", cnt);}return 0; }

　　

转载于:https://www.cnblogs.com/YDDDD/p/10300726.html

总结

以上是生活随笔为你收集整理的HDU-3038-How Many Answers Are Wrong的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。