icontofig | 发布于 2020-03-08 21:56:31 | 阅读量 809 | topsort
发布于 2020-03-08 21:56:31 | topsort
SWERC 2019-20 Problem G. Swapping Places 拓扑排序
题目大意有s种动物排成一个长度为n的队伍,有l种朋友关系a b,动物a和动物b为朋友可以互相交换位置,但是当且仅当这两种动物在相邻位置时。 问在所有的可能交换位置的方案后,序列最小的字典序排列是什么。 题解挺难想的一个题,看题解只有一句话,看代码看了好久才想明白。 通过动物之间的朋友关系,我们可以确定可以互相交换的有哪些位置,也可以确定哪些动物的相对位置是不能发生改变的。 于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点,来进行拓扑排序(当然是字典序更小的动物为更优先序的) 首先给所有物种的名字排序保证是字典序,然后用二维数组E:0 表示两个物种可以交换(是朋友),1表示不能交换
继续阅读
icontofig | 发布于 2019-10-12 13:42:57 | 阅读量 140 | 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 | 阅读量 307 | 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 | 阅读量 151 | 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 | 阅读量 416 | 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
继续阅读