首页 > 其他分享 >20240916总结

20240916总结

时间：2024-09-16 21:14:33浏览次数：9  
标签：总结 int top 20240916 scc dfn low include

不积跬步，无以千里。

这两天主要是复习了图的连通性相关的题+听了youwike哥哥讲课。

先是复习了缩点，割点，割边，点双，边双，2-SAT，感觉比较需要注意的是割点的那个第一个节点的判断，写题的时候总是容易忘。然后又写了几道练习题。

  • 缩点
#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;

int n, m, tot, cnt, top, scc, ans;
int a[N], s[N], sta[N], x[N], y[N], f[N];
int head[N], dfn[N], low[N], col[N];
bool vis[N];
struct Map { int to, nxt; } e[N << 1];

void add(int u, int v) {
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++cnt;
	vis[u] = 1, sta[++top] = u;
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if(vis[v]) 
			low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]) {
        scc++;
        while(sta[top + 1] != u) {
            col[sta[top]] = scc;
            s[scc] += a[sta[top]];
            vis[sta[top--]] = 0;
        }
    }
}

void dfs(int x) {
	if(f[x]) return;
	f[x] = s[x];
	int maxx = 0;
	for(int i = head[x]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(!f[v]) dfs(v);
		maxx = max(maxx, f[v]);
	}
	f[x] += maxx;
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1, u, v; i <= m; ++i)
		cin >> x[i] >> y[i], add(x[i], y[i]);
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= tot; ++i) e[i] = {0, 0};
	for(int i = 1; i <= n; ++i) head[i] = 0;
	tot = 0;
	for(int i = 1; i <= m; ++i) 
		if(col[x[i]] != col[y[i]]) add(col[x[i]], col[y[i]]);
	for(int i = 1; i <= scc; ++i) {
		if(!f[i]) 
			dfs(i), ans = max(ans, f[i]);
	}
	cout << ans << endl;
	return 0;
}
  • 点双
#include <iostream>
#include <vector>

using namespace std;
const int N = 4e6 + 10;

int n, m, tot, top, cnt, scc;
int s[N];
int head[N], dfn[N], low[N];
vector <int> ans[N];
struct Map { int to, nxt; } e[N << 1];

void add(int u, int v) {
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

void tarjan(int u, int fa) {
	int son = 0;
	low[u] = dfn[u] = ++cnt;
	s[++top] = u;
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(!dfn[v]) {
			son++, tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
				scc++;
				while(s[top + 1] != v) ans[scc].push_back(s[top--]);
				ans[scc].push_back(u);
			}
		} else if(v != fa) low[u] = min(low[u], dfn[v]);
	}
	if(fa == 0 && son == 0) ans[++scc].push_back(u);
}

int main() {
	cin >> n >> m;
	for(int i = 1, u, v; i <= m; ++i)
		cin >> u >> v, add(u, v), add(v, u);
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) top = 0, tarjan(i, 0);
	cout << scc << endl;
	for(int i = 1; i <= scc; ++i) {
		cout << ans[i].size() << ' ';
		for(int j = 0; j < ans[i].size(); ++j) 
			cout << ans[i][j] << ' ';
		cout << endl;
	}
	return 0;
}
  • 2-SAT
#include <iostream>

using namespace std;
const int N = 2e6 + 10;

int n, m, tot, cnt, scc, top;
int head[N], dfn[N], low[N];
int s[N], col[N];
bool vis[N];
struct Map { int to, nxt; } e[N << 1];

void add(int u, int v) {
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++cnt;
	vis[u] = 1, s[++top] = u;
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(!dfn[v]) 
			tarjan(v), low[u] = min(low[u], low[v]);
		else if(vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		++scc;
		while(u != s[top + 1]) {
			col[s[top]] = scc;
			vis[s[top--]] = 0;
		}
	}
} 

int main() {
	cin >> n >> m;
	for(int i = 1, u, v, vu, vv; i <= m; ++i) {
		cin >> u >> vu >> v >> vv;
		add(u + n * (vu & 1), v + n * (vv ^ 1));
		add(v + n * (vv & 1), u + n * (vu ^ 1));
	}
	for(int i = 1; i <= (n << 1); ++i) 
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; ++i)
		if(col[i] == col[n + i]) 
			return cout << "IMPOSSIBLE" << endl, 0;
	cout << "POSSIBLE" << endl;
	for(int i = 1; i <= n; ++i)
		cout << (col[i] < col[n + i]) << ' ';
	return 0;
}
  • 满汉全席
    把\(m\)和\(h\)看成两个对立的限制然后直接像2-SAT一样建图就行了，要注意的是对于每组数据都要全部初始化。
#include <iostream>
#include <cstring>

using namespace std;
const int N = 2e6 + 10;

int T, n, m, tot, cnt, scc, top;
int head[N], dfn[N], low[N];
int s[N], col[N];
char s1[110], s2[110];
bool vis[N];
struct Map { int to, nxt; } e[N << 1];

void add(int u, int v) {
	e[++tot] = {v, head[u]};
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++cnt;
	vis[u] = 1, s[++top] = u;
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(!dfn[v]) 
			tarjan(v), low[u] = min(low[u], low[v]);
		else if(vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		++scc;
		while(u != s[top + 1]) {
			col[s[top]] = scc;
			vis[s[top--]] = 0;
		}
	}
} 

void Main() {
	cin >> n >> m;
	for(int i = 1; i <= tot; ++i) e[i] = {0, 0};
	memset(head, 0, sizeof(head)), memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low)), memset(s, 0, sizeof(s));
	memset(col, 0, sizeof(col)), memset(vis, 0, sizeof(vis));
	tot = cnt = scc = top = 0;
	for(int i = 1, u, v, vu, vv; i <= m; ++i) {
		cin >> s1 >> s2, u = v = 0;
		int lu = strlen(s1), lv = strlen(s2);
		vu = (s1[0] == 'm'), vv = (s2[0] == 'm');
		for(int j = 1; j < lu; ++j) u = u * 10 + s1[j] - '0';
		for(int j = 1; j < lv; ++j) v = v * 10 + s2[j] - '0';
		add(u + n * (vu & 1), v + n * (vv ^ 1));
		add(v + n * (vv & 1), u + n * (vu ^ 1));
	}
	for(int i = 1; i <= (n << 1); ++i) 
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; ++i)
		if(col[i] == col[n + i]) 
			return cout << "BAD" << endl, void();
	cout << "GOOD" << endl;
}

int main() {
	cin >> T;
	while(T--) Main();
	return 0;
}
  • Redundant Paths G
    因为是双向边，所以缩点之后就肯定是一棵树，然后要至少度数是2，所以最好的方法就是每两个缩点之后的叶子节点连边，所以答案就是\((s-1)/2\)(s是叶子节点个数)
#include <iostream>
#include <vector>

using namespace std;
const int N = 2e6 + 10;

int n, m, tot = 1, top;
int cnt, scc, ans;
int head[N], u[N], v[N], d[N];
int dfn[N], low[N], s[N], col[N];
bool vis[N];
struct Map { int to, nxt; bool flag; } e[N * 2];

void add(int u, int v) {
	e[++tot] = {v, head[u], 0};
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++cnt;
	s[++top] = u;
	for(int i = head[u]; i; i = e[i].nxt) {
		if(vis[i]) continue;
		vis[i] = vis[i ^ 1] = 1;
		int v = e[i].to;
		if(!dfn[v]) 
			tarjan(v), low[u] = min(low[u], low[v]);
		else low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		++scc;
		while(u != s[top + 1]) col[s[top--]] = scc;
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) 
		cin >> u[i] >> v[i], add(u[i], v[i]), add(v[i], u[i]);
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= m; ++i) 
		if(col[u[i]] != col[v[i]]) d[col[u[i]]]++, d[col[v[i]]]++;
	for(int i = 1; i <= scc; ++i) 
		if(d[i] == 1) ans++;
	cout << (ans + 1) / 2 << endl;
	return 0;
}
  • Running In The Sky
    缩点板子题，就多维护一个路径最大值就行了。
#include <iostream>
#include <vector>

using namespace std;
const int N = 2e6 + 10;

int n, m, tot = 1, top;
int cnt, scc, ans;
int head[N], u[N], v[N], d[N];
int dfn[N], low[N], s[N], col[N];
bool vis[N];
struct Map { int to, nxt; bool flag; } e[N * 2];

void add(int u, int v) {
	e[++tot] = {v, head[u], 0};
	head[u] = tot;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++cnt;
	s[++top] = u;
	for(int i = head[u]; i; i = e[i].nxt) {
		if(vis[i]) continue;
		vis[i] = vis[i ^ 1] = 1;
		int v = e[i].to;
		if(!dfn[v]) 
			tarjan(v), low[u] = min(low[u], low[v]);
		else low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		++scc;
		while(u != s[top + 1]) col[s[top--]] = scc;
	}
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) 
		cin >> u[i] >> v[i], add(u[i], v[i]), add(v[i], u[i]);
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= m; ++i) 
		if(col[u[i]] != col[v[i]]) d[col[u[i]]]++, d[col[v[i]]]++;
	for(int i = 1; i <= scc; ++i) 
		if(d[i] == 1) ans++;
	cout << (ans + 1) / 2 << endl;
	return 0;
}
  • 菜肴制作
    容易发现，如果直接按照限制做的话是不对的，因为不是要最后字典序最小，而是要当前没有输出的数尽量靠前。但是可以发现越大的书越靠后肯定是不劣的，所以只用倒着拓扑就行了。
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int N = 1e5 + 10;

int T, n, m, cnt;
int in[N], ans[N];
vector <int> v[N];
priority_queue <int> q;

void Main() {
	cin >> n >> m;
	cnt = 0;
	for(int i = 1; i <= n; ++i)
		in[i] = ans[i] = 0, v[i].clear();
	for(int i = 1, u, vv; i <= m; ++i) {
		cin >> u >> vv;
		in[u]++, v[vv].push_back(u);
	}
	for(int i = 1; i <= n; ++i)
		if(!in[i]) q.push(i);
	while(!q.empty()) {
		int u = q.top();
		q.pop();
		for(int i = 0; i < v[u].size(); ++i) {
			int y = v[u][i];
			in[y]--;
			if(!in[y]) q.push(y);
		}
		ans[++cnt] = u;
	}
	if(cnt < n) return cout << "Impossible!" << endl, void();
	for(int i = cnt; i; --i) cout << ans[i] << ' ';
	cout << endl;
}

int main() {
	cin >> T;
	while(T--) Main();
	return 0;
}

感觉缩点很好使啊，就是考试没见过

标签：总结,int,top,20240916,scc,dfn,low,include
From： https://www.cnblogs.com/roselu/p/18416600

相关文章

  • 今日总结1.1
    第一章：软件开发概述     1.1软件与程序1.1.1从程序到软件 计算机程序（简称程序）是为了解决某个特定问题而用程序设计语言描述的适合计算机处理的语句序列；软件是能够完成预定功能和性能的可执行的程序和使程序正常执行所需要的数据，加上描述软件开发过程及其管理、程序的操......
  • 今日总结1.2
    一、软件设计模式的产生背景“设计模式”这个术语最初并不是出现在软件设计中，而是被用于建筑领域的设计中。1977年，美国著名建筑大师、加利福尼亚大学伯克利分校环境结构中心主任克里斯托夫·亚历山大（ChristopherAlexander）在他的著作《建筑模式语言：城镇、建筑、构造（APatternLa......
  • 今日总结1.3
    ‌软件构造主要学习设计模式、软件结构、模块化软件构造、面向对象的软件构造、软件重构与交付等方面的知识。‌‌设计模式‌是软件构造中的一个重要部分，它涉及如何针对接口编程而不是针对实现编程，旨在实现对象之间的松耦合设计，以及如何使用面向对象设计原则进行程序编码。学习设......
  • 2024.9.16 下午 总结（考 DS）
    T1做法1：莫队。（考虑一个数的出现次数变化时的影响。）应该可以直接做，似乎也可以正难则反（见做法2）。做法2：[扫描线]（？）。按询问右端点排序。记一下每个位置前面最近的和它权值相同的位置。一种是直接做，分讨。一种是正难则反：算前缀和；算出现次数为\(2\)的数的贡献之和，减去这部分贡献。......
  • 列表与克隆体专题 scratch 20240916_182231
    体验克隆体变量scratch20240916_153936_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/12031738数据的容器列表scratch20240916_155811_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/12031757多组列表共同表达同一数据sc......
  • 多组列表共同表达同一数据 scratch 20240916_170510
    需求如果点击空格就会产生一个克隆体克隆体会随机位置克隆体它会有自己的id同时克隆体会有自己的座标要求我们使用三个列表分别记录他们的id，x，y坐标同时如果点击了某一个克隆体那么就从列表中把它相对应的一组数据删除功能克隆体的id三个列表一个列表存id一个列表......
  • 数据的容器 列表 scratch 20240916_155811
    什么是列表列表是数据的容器创建列表列表添加内容清空内容查找数据根据位置查找数据修改数据删除数据根据下标删除数据遍历所有数据让主角依次把所有的数据都说一遍......
  • 体验克隆体变量 scratch 20240916_153936
    需求本体产生三个克隆体每个克隆体都会说出自己的血量如果鼠标点击这个克隆体角色克隆体的血量就减少同时他说出来的数据也就会变小制作克隆体变量克隆体变量一定要是私有的当本体被克隆时这个私有的变量也会被克隆不过克隆后就各是各的数据了最终代码......
  • 错误总结反思
    0.概述这篇文章旨在记录我真实经历过的一些值得反思的错误，可能是自己犯的错误，也可能是其他人犯的错误。但是都是一些值得反思的问题，文章结构可能会比较乱，以后记录的问题多了肯定会再进行梳理。1.vectorsize为0在做"求TopK"算法问题时，遇到结果错误问题。经过调试发现那个长度为......
  • 动态规划理论总结
    三个特征最优子结构问题最优解包含子问题的最优解，即可以通过子问题得到最优解。无后效性有两层含义：在后面的推到过程中，只关心前面的状态值，不关心这个状态是怎么一步步推导出来的。前面的状态如果已经确定，就不会收到后面状态影响子问题重叠不同的决策序列，到达某个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99