111qqz的小窝

老年咸鱼冲锋!

树边，前向边，后向边，横叉边

转载自： 原文链接 树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树

Posted by 111qqz Tuesday, April 12, 2016

bc #74 div1 1001 || hdu 5636 Shortest Path (floyd？)

题目链接 题意：有一条n个节点的链，节点i和节点j的距离为abs(i-j) 现在新增加三条边，距离也都为1，然后给出m个询问，每组询问给出两个点

Posted by 111qqz Thursday, March 31, 2016

bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题，并查集or 二分+bfs验证连通性)

题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。 先说一种：做法是把格子看成点，可以

Posted by 111qqz Monday, March 28, 2016

bc #73 B || hdu 5631 Rikka with Graph （并查集判断无向图的连通性）

http://acm.hdu.edu.cn/showproblem.php?pid=5631 题意;给出一张n个点n+1（n<=100）条边的无向图，现在删除若干条边（至少一条边），问删完之后图依然联通的方案数。 思路：分析可知

Posted by 111qqz Friday, March 4, 2016

hdoj 5606 ||bc #68 div 2 B tree

http://acm.hdu.edu.cn/showproblem.php?pid=5606 题意：一棵树，边权为0或者1，问对于每个点，距离它最近的点（包括自身）的个数是多少。输出将所有点的答案异或后的值。 思路：由于包括自身，自己

Posted by 111qqz Saturday, January 2, 2016

codeforces 22 C. System Administrator

http://codeforces.com/contest/22/problem/C 题意：要求用n个点m条边构造一个不允许有重边的图，满足当去掉点v的时候，剩下的n-1个不联通。如果有答案输出任意，没答案输出-1. 思路：首

Posted by 111qqz Wednesday, December 30, 2015

codeforces #333 div 2 C. The Two Routes

http://codeforces.com/problemset/problem/602/C 题意：给出n个城镇，m条双向铁路，对于任意不同的x,y，如果x,y之间没有铁路，那么一定有双向公路。train只能走铁路，bus只能走公路

Posted by 111qqz Tuesday, December 22, 2015

poj 3687 Labeling Balls

http://poj.org/problem?id=3687 题意：给定几个标签球的重量大小关系，求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。 （输出是每个球第几重，而不是几号球比

Posted by 111qqz Saturday, December 19, 2015

poj 3660 Cow Contest (floyd,传递闭包)

http://poj.org/problem?id=3660 题意：给定n个奶牛，m个奶牛的关系，a,b表示a比b强…问能确定多少个奶牛的排名。 思路：最重要的一点是。。能确定奶牛i的排名

Posted by 111qqz Thursday, December 17, 2015

hdu 2647 rewards

http://acm.hdu.edu.cn/showproblem.php?pid=2647 题意：老板要给很多员工发奖金， 但是部分员工有个虚伪心态， 认为自己的奖金必须比某些人高才心理平衡； 但是老板很人道， 想满足所有人的要求， 并且很

Posted by 111qqz Thursday, December 17, 2015

hdu 3342 Legal or Not

http://acm.hdu.edu.cn/showproblem.php?pid=3342 裸题。 注意有重边。 /* *********************************************** Author :111qqz Created Time :2015年12月17日 星期四 19时29分00秒 File Name :code/hdoj/3342.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define

Posted by 111qqz Thursday, December 17, 2015

codeforces 574B Bear and Three Musketeers

http://codeforces.com/problemset/problem/574/B 题意：给定一个无相图。选出三个点，使得这三个点之间互相有边相连，且三个点的度数之和最小。 思路：暴力出奇迹。复杂度o(n2+n*m) /* *********************************************** Author :111qqz

Posted by 111qqz Friday, December 11, 2015

codeforces 510 C. Fox And Names

http://codeforces.com/contest/510/problem/C 题意：给定n个字符串。问是否存在一种字母顺序，使得这n个字符串的顺序满足字典序（自定义的）。如果有多种顺序，输出字典序（标准的）最小的。 思

Posted by 111qqz Wednesday, December 9, 2015

hdu 2094 产生冠军

题意：给定n组u关系。每组表示a战胜b。。问根据这些关系能否确定冠军。 思路：如果a战胜b就从a连一条指向b的边。那么能确定冠军的条件就变成了

Posted by 111qqz Wednesday, December 9, 2015

hdoj 1285 确定比赛名次

http://acm.hdu.edu.cn/showproblem.php?pid=1285 题意： 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从

Posted by 111qqz Tuesday, December 8, 2015

codeforces 129 B. Students and Shoelaces

http://codeforces.com/contest/129/problem/B 题意：n个点。m条边。每一次会将图中度为1的点加入到等待队列中。然后一起删掉，记为一次操作。当删掉一个点的时候，与它相连的边也全部删掉。问

Posted by 111qqz Saturday, December 5, 2015

FEATURED TAGS
bfs binary-search brute-force c++ dfs dp greedy hash km kmp leetcode math number-theory rmq sg函数 stl tensorflow 二分图最佳匹配 分块 前缀和 匈牙利算法 区间dp 博弈论 后缀自动机 图论 字符串 快速幂 数位dp 构造 树状数组 概率 模拟 母函数 矩阵 离散化 线段树 计算几何
ABOUT ME
avatar

ex-ACMer@HUST, researcher@SenseTime

FRIENDS