# 带权并查集 POJ 1182 食物链 & HDU 3047 Zjnu Stadium

POJ 1182 食物链:


#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
int root[N], rank[N], n, m;
void init()
{
for(int i = 0; i<n; i++)
root[i] = i, rank[i] = 0;
}
int Find(int x)
{
if(x == root[x])
return x;
int pre = root[x];
root[x] = Find(root[x]);
rank[x] = (rank[x] + rank[pre])%3;
return root[x];
}
void join(int d, int u, int v)
{
int x = Find(u), y = Find(v);
if(x == y) return ;
root[x] = y;
rank[x] = (rank[v] + d -  rank[u] + 3)%3;
return ;
}
bool istrue(int d, int u, int v)
{
int x  = Find(u), y = Find(v);
if(u > n || v > n || d == 2 && u == v)
return false;
if(x != y)
return true;
else
{
return rank[u] ==  (rank[v] + d + 2)%3;
}
}
int main()
{
int d, u, v;
scanf("%d%d", &n, &m);
init();
int ans = 0;
while(m--)
{
scanf("%d%d%d", &d, &u, &v);
if(istrue(d, u, v))
join(d-1, u, v);
else ans ++;
}
printf("%d\n", ans);
return 0;
}


#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#define endl '\n'
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
int root[N], Rank[N], n, m, ans;
void init()
{
for(int i = 0; i<=n; i++)
root[i] = i, Rank[i] = 0;
ans = 0;
}
int Find(int x)
{
if(x == root[x])
return x;
int pre = root[x];
root[x] = Find(root[x]);
Rank[x] = (Rank[x] + Rank[pre])%300;
return root[x];
}
void join(int d, int u, int v)
{
int x = Find(u), y = Find(v);
root[y] = x;
Rank[y] = (Rank[u] + d - Rank[v] + 300)%300;
}
int istrue(int d, int u, int v)
{
int x = Find(u), y = Find(v);
if(x != y) return 1;
return Rank[v] == (Rank[u] + d)%300;
}
int main()
{
int u, v, d;
while(~scanf("%d%d", &n, &m))
{
init();
while(m--)
{
scanf("%d%d%d", &u, &v, &d);
if(istrue(d, u, v))
join(d, u, v);
else ans ++;
}
printf("%d\n", ans);
}
return 0;
}

### 相关文章

1. Four to five portions of this veggie juice must be consumed every week to obtain the desired result. Once you discover the top natural treatments, it is possible to once again have full charge of your sexual pleasures.
http://www.generiqueviagrafr.fr/vente-viagra-usa

Aburedorge 回复