程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> HDU 3047 Zjnu Stadium（帶權並查集）

HDU 3047 Zjnu Stadium（帶權並查集）

編輯：關於C

思路：注意，行數是無限的，因此，兩個人可以同時都相距另一個人x遠（相距x列，不在同一行），也就是說，出現矛盾的唯一地方就是在於，現在說的兩個人相距的距離和之前說的矛盾。那麼怎麼判斷矛盾呢，由於每個人之間有間接關聯性，因此，我們需要處理一個集合的距離問題，所以用帶權並查集就可以很好的處理。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 50000 + 10;
int T,n,m,p[maxn],dist[maxn];
void init(int n) {
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        dist[i] = 0;
    }
}
int _find(int x) {
    if(p[x] == x) return p[x];
    int fa = p[x];
    p[x] = _find(p[x]);
    dist[x] += dist[fa]; // 路徑壓縮的時候順便維護每個點到祖先的距離
    return p[x];
}
inline bool BIN(int a, int b, int c) {
    int x = _find(a);
    int y = _find(b);
    if(x == y) {
        if(dist[a] + c != dist[b]) return false; // 判斷是否矛盾
        return true;
    }
    p[y] = x;
    dist[y] = dist[a] - dist[b] + c; // 計算相對距離， a和b相距c， 那麼根據向量加減， 可以求出dist[y]。具體可以畫個圖看看
    return true;
}
int a, b, c;
int main() {
    while(~scanf("%d%d",&n,&m)) {
        init(n);
        int ans = 0;
        while(m--) {
            scanf("%d%d%d",&a,&b,&c);
            if(!BIN(a, b, c)) ++ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}