欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[动态图]

程序员文章站 2024-01-19 12:48:40
...

给一个图,每一条边有一个消失的时刻,询问1~K每个时刻两两可达的点对有多少对?

题目链接:http://poj.openjudge.cn/practice/C15C/

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define maxn 200010

using namespace std;
typedef long long ll;

ll ans;
int N, M, K;
int h[maxn], cnt;
struct Edge{int u, v, nxt;}edge[maxn];
void add(int x, int u, int v){
	edge[++ cnt] = (Edge){u, v, h[x]};
	h[x] = cnt;
}

void init(){
	memset(h, 0, sizeof h);
	ans = cnt = 0;
}

struct Node{
	int u, v, cntu, cntv, ranku, rankv;
	Node(int u = 0, int v = 0, int cntu = 0, int cntv = 0, int ranku = 0, int rankv = 0):
		u(u), v(v), cntu(cntu), cntv(cntv), ranku(ranku), rankv(rankv){}
}st[maxn];

int top;

namespace Set{
	int rank[maxn], fa[maxn], c[maxn];
	
	void Init(){
		for(int i = 1; i <= N; i ++)
		    c[i] = 1, fa[i] = i, rank[i] = 1;
	}
	
	int Findroot(int x){
		while(x != fa[x])x = fa[x];
		return x;
	}
	
	void Union(int u, int v){
        u = Findroot(u);
		v = Findroot(v);
		if(u == v)return;
		ans += (ll)c[u] * c[v];
		st[++ top] = (Node){u, v, c[u], c[v], rank[u], rank[v]};
        if(rank[u] == rank[v]){
			if(c[u] < c[v])swap(u, v);
			fa[v] = u;
			c[u] += c[v];
			rank[u] = rank[v] + 1;
			return;
		}
		if(rank[u] < rank[v])swap(u, v);
		fa[v] = u;
		c[u] += c[v];
	}
	
	int Pushback(int rtop){
		for(; top > rtop; top --){
			int u = st[top].u, v = st[top].v;
			ans -= (ll)st[top].cntu * st[top].cntv;
			fa[u] = u, fa[v] = v;
			c[u] = st[top].cntu;
			c[v] = st[top].cntv;
			rank[u] = st[top].ranku;
			rank[v] = st[top].rankv;
		}
	}
}

void cdq(int l, int r){
	if(l == r){
		printf("%lld\n", ans);
		return;
	}
	int mid = l + r >> 1, rtop = top;
	for(int i = mid + 1; i <= r; i ++)
	    for(int j = h[i]; j; j = edge[j].nxt)
			Set::Union(edge[j].u, edge[j].v);
	cdq(l, mid);
	Set::Pushback(rtop);
	for(int i = l; i <= mid; i ++)
	    for(int j = h[i]; j; j = edge[j].nxt)
	        Set::Union(edge[j].u, edge[j].v);
	cdq(mid + 1, r);
	Set::Pushback(rtop);
}

void solve(){
	init();
	int u, v, c;
	Set::Init();
	for(int i = 1; i <= M; i ++){
		scanf("%d%d%d", &u, &v, &c);
		add(c, u, v);
	}
	cdq(1, K);
}

int main(){
	while(~scanf("%d%d%d", &N, &M, &K))
	    solve();
	return 0;
}