Tarjan算法模板&二分模板

tonyfang posted @ 2016年9月30日 20:11 in 随笔 with tags c++ OI , 640 阅读

把一些常错的板子晾出来以便于查错。

Tips:由于更新可能越来越多,使用Ctrl+F查询更方便。

1. Tarjan求割点【poj1144】

# include <stdio.h>
# include <string.h>
// # include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 260010;
int dfn[N], low[N], DFN, sz[N];
int head[N], next[M], to[M], tot;
int n, cut[N], cutp;

inline void clear() {
	tot = cutp = DFN = 0;
	memset(head, 0, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(sz, 0, sizeof(sz));
	memset(cut, 0, sizeof(cut));
}

inline void add_e(int u, int v) {++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;}
inline void adde(int u, int v) {add_e(u, v); add_e(v, u);}

# define fago {if(to[i] == fa) continue;}
# define min(a,b) ((a)<(b)?(a):(b))

inline void tarjan(int x, int fa) {
	dfn[x]=low[x]=++DFN; sz[x] = 0;
	for (int i=head[x]; i; i=next[i]) {
		++ sz[x];
		fago
		if(dfn[to[i]] != 0) {
			low[x] = min(low[x], dfn[to[i]]);
		} else {
			tarjan(to[i], x);
			low[x] = min(low[x], low[to[i]]);
			if(x == 1) {
				if(sz[x] >= 2) cut[x] = 1;
			}
			else if(low[to[i]] >= dfn[x]) cut[x] = 1;
		}
	}
}

int main() {
	//int Case = 0;
	while(~scanf("%d", &n) && n) {
		clear(); //++Case;
		int u, v;
		while(~scanf("%d", &u) && u) {
			char str;
			while(~scanf("%c", &str) && str != '\n') {
				scanf("%d", &v);
				adde(u, v);
			}
		}
		tarjan(1, 0);
		for (int i=1; i<=n; ++i) cutp += cut[i];
		printf("%d\n", cutp);
	}
	return 0;
}

2. Tarjan求割边

# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 260010;
int dfn[N], low[N], DFN;
int head[N], next[M], to[M], tot;
int n, m, cutb;
struct edge{int u, v;}e[M];

inline void add_e(int u, int v) {++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;}
inline void adde(int u, int v) {add_e(u, v); add_e(v, u);}

# define fago {if(to[i] == fa) continue;}
# define min(a,b) ((a)<(b)?(a):(b))

inline void tarjan(int x, int fa) {
	dfn[x]=low[x]=++DFN;
	for (int i=head[x]; i; i=next[i]) {
		fago
		if(!dfn[to[i]]) {
			tarjan(to[i], x);
			low[x] = min(low[x], low[to[i]]);
		} else low[x] = min(low[x], dfn[to[i]]);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1, u, v; i<=m; ++i) {
		scanf("%d%d", &u, &v);
		adde(u, v);
		e[i].u=u, e[i].v=v;
	}
	tarjan(1, 0);
	for (int i=1; i<=m; ++i) {
		if(dfn[e[i].u] > dfn[e[i].v]) swap(e[i].u, e[i].v);
		if(low[e[i].v] > dfn[e[i].u]) ++cutb;
	}
	printf("%d\n", cutb);
	return 0;
}

3. Tarjan缩点(hdu1827)

Tips:缩点的tarjan,dfs的时候不需要弄fa。也就是代码里没有fago

至于为啥#define next nxt 因为hdu用next变量名有问题。

# include <stdio.h>
# include <string.h>
// # include <bits/stdc++.h>

using namespace std;

# define next nxt

const int N = 100010, M = 260010;
int dfn[N], low[N], DFN, d[N];
int head[N], next[M], to[M], tot;
int n, m, belong[N], scc, du[N];
int st[M], stn;
bool ins[N];
int pers[N];
struct edge{int u, v;}e[M];

inline void clear() {
	tot = stn = DFN = scc = 0;
	memset(head, 0, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(du, 0, sizeof(du));
	memset(ins, 0, sizeof(ins));
	memset(pers, 127/3, sizeof(pers));
}

inline void add_e(int u, int v) {++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;}
inline void adde(int u, int v) {add_e(u, v); add_e(v, u);}

# define min(a,b) ((a)<(b)?(a):(b))

inline void tarjan(int x) {
	dfn[x]=low[x]=++DFN;
	st[++stn] = x; ins[x] = 1;
	for (int i=head[x]; i; i=next[i]) {
		if(!dfn[to[i]]) {
			tarjan(to[i]);
			low[x] = min(low[x], low[to[i]]);
		} else if(ins[to[i]]) low[x] = min(low[x], dfn[to[i]]);
	}
	if(dfn[x] == low[x]) {
		++scc;
		while(stn>0) {
			int tmp = st[stn];
			belong[tmp] = scc;
			ins[tmp] = 0;
			--stn;
			if(tmp == x) break;
		}
	}
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		clear();
		for (int i=1; i<=n; ++i) scanf("%d", &d[i]);
		for (int i=1, u, v; i<=m; ++i) {
			scanf("%d%d", &u, &v);
			add_e(u, v);
			e[i].u=u, e[i].v=v;
		}
		for (int i=1; i<=n; ++i) {
			if(dfn[i] == 0) 
				tarjan(i);
		}
		for (int i=1; i<=m; ++i) {
			if(belong[e[i].u] == belong[e[i].v]) continue;
			du[belong[e[i].v]] ++;
		}
		for (int i=1; i<=n; ++i) 
			if(du[belong[i]] == 0) pers[belong[i]] = min(pers[belong[i]], d[i]);
		int ans1 = 0, ans = 0;
		for (int i=1; i<=scc; ++i)
			if(du[i] == 0) ans += pers[i], ++ans1;
		printf("%d %d\n", ans1, ans);
	}

	return 0;
}

 

4. 二分

十个二分九个错。这里晾一份不会错的二分(不用想什么+1,-1之类的)

 

int l, r, mid, ans = 0;
l = From, r = To;
while(1) {
    if(r-l<=3) {
        for (int i=l; i<=r; ++i) 
            if(check(i)) { ans = i; break; }
        break;
    }
    mid = l+r>>1;
    if(check(mid)) l = mid;
    else r = mid;
}
Answer = ans;

 

 

 

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter