icontofig | 发布于 2019-10-12 13:42:57 | 阅读量 120 | bitset topsort
发布于 2019-10-12 13:42:57 | bitset topsort
牛客国庆欢乐赛5 2017四川省赛 D.Dynamic Graph  bitset加速 + topsort
题目大意给定一个n个点的DAG(有向无环图),每个点一开始都是白色,每一次操作会改变一个指定的点的颜色,并询问当前有多少对白点对(u,v)互相可达(存在一条从u到v的有向路径使得路径上全部为白色的点)。 题解可以认为黑色点与其他点都不连通。 所以我们每一次更改点的颜色实际都是再更改图的联通关系。 我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系(这时候就通过位运算或|来代替Floyd原先的+就好了,因为位运算或即为逻辑加操作)。 但是我们发现这样复杂度是不对的…… 这三种最快的topsort复杂度也是O(qnm)的,明显不符合我们的复杂度要求。 这时候我
继续阅读
icontofig | 发布于 2019-07-07 21:56:00 | 阅读量 262 | topsort DP
发布于 2019-07-07 21:56:00 | topsort DP
洛谷P1137 旅行计划
题解别问我为什么写这么水的题解,问就是为了那门水的不行的专业选修课。 很简单,这个图肯定是个DAG(请不要问为什么,自己看一下题目描述。。。) 然后我们在这个DAG上按拓扑序来进行DP就可以了,因为入度为0的点一定最多游览一个,然后不断类似SPFA最长路一样的进行DP,就可以求出到某个城市最多可以游览的城市数目了。 代码#include <bits/stdc++.h> using namespace std; int get_num(){ int num = 0; char c; bool flag = false; while((c = getch
继续阅读
icontofig | 发布于 2019-02-26 18:14:48 | 阅读量 137 | topsort
发布于 2019-02-26 18:14:48 | topsort
DescriptionTeacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road. He wants develop this kingdom from one city to one city. Teacher Mai now is considering developing the city w. And he hopes that for every c
继续阅读
icontofig | 发布于 2019-02-07 01:05:31 | 阅读量 365 | 2-SAT tarjan topsort
发布于 2019-02-07 01:05:31 | 2-SAT tarjan topsort
DescriptionYou are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.Consider a partition of V into two
继续阅读