Tarjan算法模板&二分模板

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

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

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;

 

 

 

 

 

 

 

li9.in 说:
2023年4月20日 19:43

people of all ages, as we plan to publish news divided into General, Political, Crime, Sports, Entertainment, Education, and World News categories.Our reporting team plans to provide the Education & Recruitment li9.in Update for all age groups and to present the actual picture of recent events through inside coverage. Our goal would be to meet the requirements.

boardmodelpaper.com 说:
2024年1月10日 13:52

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


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