永远鲜红的幼月

图论

CF(19) dp(6) gcd的应用(1) sort(4) spfa(1) 二分(12) 几何(1) 博弈(2) 固定算法(1) 套题(5) 字符串匹配(1) 并查集(4) 思维(2) 搜索(4) 数学题(2) 数据结构(10) 数论(4) 未归档(192) 树状数组(1) 状压DP(1) 科普(3) 线段树(2) 网络流(3) 计算几何(4) 计算几何学习(17) 贪心(1) 题解(1)

/ 注册

全部文章 / 图论（共11篇）

HDU-3078-Network（LCA+暴力排序）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3078 题目大意：给出n个节点，n-1条边，q次询问。每个节点都有自己的值。然后是n-1条边。之后是q次查询，有两种状态，k==0，将a的值赋为b，k>0查询a~b最短路上面第k大的值。思路：...

2019-04-26

0 490

POJ-1236-Network of Schools（Tarjan强联通+缩点）

题目链接：http://poj.org/problem?id=1236 题目大意：给出n个点，表示n个学校。接下来是n行，输入每个点的子节点，以0结尾。表示学校i和其子节点的单向通信。两个问题： A：输出最少需要向多少个学校传递数据，才可以保证所有的学校都能收到数据。 B：最少需要加多少条...

2019-04-25

0 548

POJ-2186-Popular Cows（Tarjan强联通，缩点）

题目链接：http://poj.org/problem?id=2186 题目大意：给出n个点m条边，组成一个有向图。定义a->b表示a崇拜b，a崇拜b，b崇拜c，那么a也崇拜c。我们要找出有多少个人，被除了本身外所有的人崇拜。输出个数。思路：找出这个图的强联通分量，同一个强联通分量的...

2019-04-25

0 509

HDU-3666-THE MATRIX PROBLEM（差分约束系统）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3666 题目大意：一个n*m的矩阵和两个数L，U，对于矩阵中的每个元素，存在两个数组an，bn，使得L<=arr[i][j]*a[i]/b[j]<=U；如果存在这样两个数组，输出YES，否则...

2019-02-17

0 581

POJ-3169-Layout，HDU-3592-World Exhibition（线性约束，板子）

题目链接：http://poj.org/problem?id=3169 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3592 题目大意：n头牛，编号1~n，给出ml个关系（牛与牛之间最大的距离）md个关系（牛与牛之间最小的距离），编号小的总在编号...

2019-02-12

0 496

POJ-3660-Cow Contest（floyd变形）

题目链接：http://poj.org/problem?id=3660 题目大意：n头奶牛，给出这n头奶牛之间的两两关系，然后我们要得出能确定多少头奶牛的排名。思路：只要这头奶牛跟其他的n-1头奶牛都有关系，那么我们就能确定着头奶牛的排名，一开始碰见这道题的时候一点思路都没有，感觉bfs+df...

2019-02-09

0 429

二分图的学习总结

今天离散课老师讲了二分图（其实好像上节课就讲了，我似乎翘课了嘤嘤嘤），然后我就复习，总结一下：首先是百度百科给出的概念：二分图，又叫二部图，是图论中的一种特殊模型。设：G=(v,e)是一个无向图，如果顶点v可分割成两个互不相交的子集（A,B）并且图中的每条边(i,j)所关联的两个顶...

2018-12-17

0 599

ACM-ICPC 2018 南京赛区网络预赛-L-Magical Girl Haze-（分层最短路）

题目链接：https://nanti.jisuanke.com/t/31001 There are NN cities in the country, and MM directional roads from uu to v(1\le u, v\le n)v(1≤u,v≤n). Every ro...

2018-09-03

0 424

Aizu2249（spfa || djstr+堆优化）两个参数的最短路

题目链接：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249 Road Construction King Mercer is the king of ACM kingdom. There are one capital ...

2018-07-20

0 507

HDU Today（最短路，但难点在字符与数字之间的联系）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112 Problem Description 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。...

2018-02-10

0 591