寒鸽儿のBlog

寒鸽儿gugugu~

首页 归档 标签 关于

支配树 2020-07-15

2020-07-15 9 min read # 训练日记 # Dominator Tree # CodeChef # 图论 # 并查集 # dfs

view

  1. 过了洛谷支配树的板子
  2. 过了HDU4694 ImportantSister(支配树裸题)
  3. 过了wmd支配树课件的习题CodeChef - GRAPHCNT
  4. 开始写支配树的笔记和总结(应该会咕很久)

detail

luoguP5180

事项

  1. 不要把dfn[x]的比较写成x的比较 , 不要把sdom[x]的比较写成x的比较。

code

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define VI vector<int>

using namespace std;

vector< VI > G, _G, GDOM;
VI dfn, idfn, fa;
int dfs_clock = 1;

void dfs(int pre, int cur) {
	idfn[dfs_clock] = cur;
	dfn[cur] = dfs_clock++;
	fa[cur] = pre;
	for(int ver : G[cur])
		if(!dfn[ver])
			dfs(cur, ver);
}

inline int minpt(int u, int v) {
	return dfn[u] < dfn[v] ? u : v;	
}

VI par, dat, sdom, idom;
vector< VI > buc;
int eval(int cur) {
	if(par[cur] == cur) return cur;
	int anc = eval(par[cur]);
	dat[cur] = dfn[sdom[dat[cur]]] < dfn[sdom[dat[par[cur]]]] ? dat[cur] : dat[par[cur]];
	return par[cur] = anc;
}


void lengauer_tarjan(int n) {
	for(int i = n; i; --i) sdom[i] = i, par[i] = i, dat[i] = i;
	for(int i = n; i > 1; --i) {
		int cur = idfn[i];
		for(int ver : _G[cur]) {
			if(!dfn[ver]) continue;
			eval(ver); 
			sdom[cur] = minpt(sdom[cur], sdom[dat[ver]]);
		}
		par[cur] = fa[cur]; dat[cur] = sdom[cur];
		buc[sdom[cur]].pb(cur);
		for(int ver : buc[fa[cur]]) {
			eval(ver);
			if(sdom[dat[ver]] == fa[cur]) idom[ver] = sdom[ver];
			else idom[ver] = dat[ver];
		}
		buc[fa[cur]].clear();
	}
	rep(i,1,n) {
		int cur = idfn[i]; 
		if(idom[cur] != sdom[cur]) idom[cur] = idom[idom[cur]];
	} 
}

VI ans;

void work(int cur) {
	ans[cur] = 1;
	for(int ver : GDOM[cur]) {
		work(ver);
		ans[cur] += ans[ver];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, u, v;
	cin >> n >> m;
	G.rz(n + 1); _G.rz(n + 1); GDOM.rz(n + 1); dfn.rz(n + 1); idfn.rz(n + 1); fa.rz(n + 1); par.rz(n + 1); dat.rz(n + 1); sdom.rz(n + 1); idom.rz(n + 1); buc.rz(n + 1); ans.rz(n + 1);
	while(m--) {
		cin >> u >> v;
		G[u].pb(v);
		_G[v].pb(u);
	}
	dfs(0, 1);
	lengauer_tarjan(n);
	rep(i,1,n) GDOM[idom[i]].pb(i);
	work(1);
	rep(i,1,n) cout << ans[i] << ' ';
	cout << endl;
	return 0;
}

HDU4694 Important Sister

事项

  1. 注意并查集中保存的是sdom[x]最小的点的编号而不是sdom的最小值。
  2. 有些点在流图中不可达 , 所以支配树中点的个数应为dfs后dfs_clock - 1。
  3. 初始化sdom[x] = par[x] = dat[x] = x;
  4. 不要把并查集的par[]和dfs树中的fa[]搞混淆
  5. 不要忘记清空buc[]
  6. 一个点求完在并查集中挂fa在buc中挂sdom , 但是弹出是弹出fa
  7. r无支配点 , 记idom[r] = 0
  8. 最后一步调整的过程为dfn升序

code

#include <bits/stdc++.h>

using namespace std;


typedef vector< vector<int> > Graph;

const int maxn = 56789;

Graph G, _G, DOM;
vector< vector<int> > buc;
int dfn[maxn], idfn[maxn], fa[maxn], dfs_clock = 1;
int par[maxn], dat[maxn];
int sdom[maxn], idom[maxn];

void dfs(int pre, int cur) {
	idfn[dfs_clock] = cur; dfn[cur] = dfs_clock++;
	fa[cur] = pre;
	for(int ver : G[cur]) if(!dfn[ver]) dfs(cur, ver);
}

int find(int x) {
	if(par[x] == x) return x;
	int p = find(par[x]);
	if(dfn[sdom[dat[par[x]]]] < dfn[sdom[dat[x]]]) dat[x] = dat[par[x]];
	return par[x] = p;
}

inline int eval(int x) { find(x); return dat[x]; }

void lengauer_tarjan(int n, int r) {
	memset(dfn, 0, sizeof(dfn));
	memset(idfn, 0, sizeof(dfn));
	memset(fa, 0, sizeof(fa));
	memset(idom, 0, sizeof(idom));
	dfs_clock = 1;
	dfs(0, r);
	--dfs_clock;
	for(int i = 1; i <= n; ++i) par[i] = dat[i] = sdom[i] = i;
	for(int i = dfs_clock; i > 1; --i) {
		int cur = idfn[i];
		for(int ver : _G[cur]) {
			if(!dfn[ver]) continue;
			int ev = eval(ver);
			if(dfn[sdom[cur]] > dfn[sdom[ev]]) sdom[cur] = sdom[ev];
		}
		par[cur] = fa[cur]; buc[sdom[cur]].push_back(cur);
		for(int ver : buc[fa[cur]]) {
			if(sdom[eval(ver)] == fa[cur]) idom[ver] = fa[cur];
			else idom[ver] = eval(ver);
		}
		buc[fa[cur]].clear();
	}
	for(int i = 2; i <= dfs_clock; i++) {
			int cur = idfn[i];
			if(idom[cur] != sdom[cur]) idom[cur] = idom[idom[cur]];
	}
	idom[r] = 0;
}

long long ans[maxn];
void work(int pre, int cur) {
	ans[cur] = cur + ans[pre];
	for(int ver : DOM[cur])
		work(cur, ver);
} 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, r;
	while(cin >> n >> m) {
		r = n;
		G.clear(); G.resize(n + 1);
		_G.clear(); _G.resize(n + 1);
		DOM.clear(); DOM.resize(n + 1);
		buc.clear(); buc.resize(n + 1);
		int u, v;
		while(m--) {
			cin >> u >> v;
			G[u].push_back(v);
			_G[v].push_back(u);
		}
		lengauer_tarjan(n, r);
		for(int i = 1; i <= n; ++i) {
			DOM[idom[i]].push_back(i);
		}
		memset(ans, 0, sizeof(ans));
		work(0, r);
		for(int i = 1; i < n; ++i) cout << ans[i] << ' ';
		cout << ans[n] << endl;
	}
	return 0;
}

CodeChef - GRAPHCNT

分析

原问题可转化为求支配树上lca = r的有序点对数量和
另一种count法挂了，没搞清楚为什么qaq

事项

  1. 大于号方向注意不要搞反

code

#include <bits/stdc++.h> 
#define pb push_back
#define rz resize

using namespace std;

typedef vector<int> VI;
typedef vector<VI> Graph;
typedef long long ll;

const int maxn = 123456;

Graph G, _G, DOM;
VI buc[maxn];
int dfn[maxn], idfn[maxn], fa[maxn], dfs_clock;
int par[maxn], dat[maxn];
int sdom[maxn], idom[maxn];

void dfs(int pre, int cur) {
	idfn[dfs_clock] = cur; dfn[cur] = dfs_clock++;
	fa[cur] = pre;
	for(int ver : G[cur]) if(!dfn[ver]) dfs(cur, ver);
}

int find(int x) {
	if(par[x] == x) return x;
	int p = find(par[x]);
	if(dfn[sdom[dat[x]]] > dfn[sdom[dat[par[x]]]]) dat[x] = dat[par[x]];
	return par[x] = p;
}

int eval(int x) { find(x); return dat[x]; }

void lengauer_tarjan(int n, int r) {
	dfs_clock = 1;
	dfs(0, r);
	--dfs_clock;
	for(int i = 1; i <= n; ++i) par[i] = dat[i] = sdom[i] = i;
	for(int i = n; i > 1; --i) {
		int cur = idfn[i];
		for(int ver : _G[cur]) {
			if(!dfn[ver]) continue;
			int ev = eval(ver);
			if(dfn[sdom[cur]] > dfn[sdom[ev]]) sdom[cur] = sdom[ev];
		}
		buc[sdom[cur]].pb(cur); par[cur] = fa[cur];
		for(int ver : buc[fa[cur]]) {
			int ev = eval(ver);
			if(sdom[ev] == fa[cur]) idom[ver] = fa[cur];
			else idom[ver] = ev;
		}
		buc[fa[cur]].clear();
	}
	for(int i = 2; i <= dfs_clock; ++i) {
		int cur = idfn[i];
		if(idom[cur] != sdom[cur]) idom[cur] = idom[idom[cur]];
		DOM[idom[cur]].pb(cur); 
	}
	idom[r] = 0;
}

int siz[maxn];
ll ans = 0;
void work(int cur) {
	siz[cur] = 1;
	for(int ver : DOM[cur]) {
		work(ver);
		if(cur == 1) ans += 1ll * siz[cur] * siz[ver];
		siz[cur] += siz[ver]; 
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, u, v;
	cin >> n >> m;
	G.rz(n + 1); _G.rz(n + 1); DOM.rz(n + 1);
	while(m--) {
		cin >> u >> v;
		G[u].pb(v);
		_G[v].pb(u);
	}
	lengauer_tarjan(n, 1);
	work(1);
	cout << ans << endl;
	return 0;
}
Powered by Gridea RSS