首页 > 其他分享 >LGP3183 题解

LGP3183 题解

时间:2024-09-23 21:26:50浏览次数:8  
标签:std 食物链 int 题解 出度 入度 LGP3183 cin

原题链接:P3183 [HAOI2016] 食物链

难度:Easy

根据定义,食物链是一个 DAG,所以可以进行拓扑排序。

食物链也就转化成了:图中从一个入度为 \(0\) 的点到一个出度为 \(0\) 的点的路径。

那么只需要拓扑排序求出所有起点到每个点的路径条数,然后累加出度为 \(0\) 的点的值即可。

需要注意的是,单独的一种孤立生物不算一条食物链,所以需要特判一下。

#include <bits/stdc++.h>
const int N = 1e5 + 10;

std::queue<int> q;
std::vector<int> g[N];
int n, m, ans, f[N], d[N][2];
// d[i][0/1] 表示入度/出度
// f[i] 记录以 i 为终点的路径条数

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cin >> n >> m;
	for (int i = 0, u, v; i < m; ++i) {
		std::cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
		++d[u][1], ++d[v][0]; // 更新入度出度
	}
	for (int i = 1; i <= n; ++i)
		if (!d[i][0] && d[i][1]) q.push(i), f[i] = 1; // 入度为 0 且有出度时,才不是孤立生物
	while (!q.empty()) { // 拓扑排序
		int u = q.front(); q.pop();
		for (auto v : g[u]) {
			f[v] += f[u]; // 此时到 u 的路径都可以通过 <u,v> 到达 v
			if (!--d[v][0]) q.push(v);
		}
	}
	for (int i = 1; i <= n; ++i)
		if (!d[i][1]) ans += f[i]; // 此时孤立生物 f[i] = 0
	std::cout << ans << std::endl;
	return 0;
}

标签:std,食物链,int,题解,出度,入度,LGP3183,cin
From: https://www.cnblogs.com/oier-wst/p/18427905/luogu-P3183-solution

相关文章

  • LGP1901 题解
    原题链接:P1901发射站难度:Easy。注意到"最近的且比它高",容易想到用单调栈维护每个能量发射站左右第一个比它高的,最后统计答案即可。具体的令f[i][0/1]表示能量发射站\(i\)右边/左边第一个\(h_x>h_i\)的位置\(x\)。用单调栈从左向右扫一遍,得到f[i][0]。用单调栈从右......
  • [题解] ICPC网络预选赛 2024 第二场 E Escape (含题目翻译)
    [题解]ICPC网络预选赛2024第二场EEscape(含题目翻译)tag:图论、BFS、最短路题干为原文DeepL翻译题目描述Sneaker在一个巨大的迷宫中醒来,现在他想逃离这个迷宫。通过迷宫中每个房间的地图,Sneaker了解了迷宫的结构。迷宫由......
  • 【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计
    【题解】SolutionSet-NOIP2024集训Day36dp优化+状态设计https://www.becoder.com.cn/contest/5550最后一题较难。「NOIP2023」天天爱打卡考虑dp。\(f_{i,j}\):前\(i\)天,到第\(i\)天为止连续打卡\(j\)天。有转移:\[f_{i,0}=\max(f_{i,j})\\f_{i,j}=\max(f_{i......
  • Codeforces Round 972(Div.2)题解
    CodeforcesRound972(Div.2)题解A.SimplePalindrome贪心贪心,尽可能元素数量平均,并且相同字母放在一起。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#de......
  • Codeforces Round 973 (Div.2) A-E题解
    CodeforcesRound973(Div.2)A-E题解比赛传送门A.Zhan'sBlender数学显然答案为\(\lceil\frac{n}{min(x,y)}\rceil\)。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.en......
  • 题解:AT_abc372_e [ABC372E] K-th Largest Connected Components
    题意给出\(q\)个操作。将\(u\)和\(v\)连边。问\(u\)所在的连通块中编号第\(k\)大的点。思路连通块很容易想到并查集,求第\(k\)大可以用平衡树(虽然赛时没看到\(k\le10\)),合并时将信息从将小的连通块合并到大的连通块,这样可以减少时间复杂度。什么?你不会写平衡......
  • 题解:AT_arc184_a [ARC184A] Appraiser
    题意\(1000\)个硬币中有\(10\)个假币,你每次可以询问两个位置的硬币类型是否相同,你需要用不超过\(950\)次询问找出所有假币的位置。思路将前\(990\)个硬币每\(11\)个分一组,共\(90\)组,余\(10\)个单独分一组。询问每组第\(1\)个硬币和这组后面硬币的关系。因为只......
  • CF1270H Number of Components 题解
    Description给一个长度为\(n\)的数组\(a\),\(a\)中的元素两两不同。对于每个数对\((i,j)(i<j)\),若\(a_i<a_j\),则让\(i\)向\(j\)连一条边。求图中连通块个数。支持\(q\)次修改数组某个位置的值,每次修改后输出图中连通块个数。\(n,q\le5\times10^5,1\lea_i\le10^......
  • 2024ICPC网络赛第二场题解(部分)
    前言这场相对作用大一点,最后顶着队友的怀疑压力乱搞出了C,但是后面看题解发现似乎是数据弱了跑过去,其实复杂度是队友分析的那样,是不正确的,但是毕竟是打名额的比赛,过了就是过了,这里分享一下C题的乱搞做法,以及其他题的我们队赛时代码。下面的顺序按过题顺序(也差不多是难度递增顺序)......
  • 网站程序打不开数据库错误等常见问题解决方法
    当遇到网站打不开或者数据库错误等问题时,可以按照以下步骤来诊断并解决问题:检查网站根目录:如果上传数据后显示“主机开设成功!”或“恭喜,lanmp安装成功!”,这通常是因为服务器默认放置了一个index.htm文件。此时应检查wwwroot目录内是否有自己的程序文件,并考虑删除默认的index.h......