青烟绕指柔

图论

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

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

51Nod 树的距离之和

给定一棵无根树，假设它有n个节点，节点编号从1到n, 求1-n这n个节点，到其他n-1个节点的距离之和。输入第一行包含一个正整数n (n <= 100000)，表示节点个数。后面(n - 1)行，每行两个整数表示树的边。输出每行一个整数，第i(i = 1,2,…n)行表示所有节点到...

2019-12-27

0 327

小D的剑阵

题目链接：小D的剑阵对于每一把剑，我们都有选不选的问题，也就是非黑即白的问题。于是我们可以想到最小割建图。先加上所有可以增加的价值，然后减去最小割即可。然后列出方程，解出小学生都能解的方程就可以了。 AC代码： #include<bits/stdc++.h>...

2019-12-27

0 353

Codeforces - Delivery Bears

Niwel is a little golden bear. As everyone knows, bears live in forests, but Niwel got tired of seeing all the trees so he decided to move to the city...

2019-12-27

0 524

Olympiad in Programming and Sports

There are n students at Berland State University. Every student has two skills, each measured as a number: ai — the programming skill and bi — the spo...

2019-12-27

0 798

Machine Programming

One remarkable day company “X” received k machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessfu...

2019-12-27

0 347

最小割树(Gomory-Hu Tree)

最小割树的定义：定义一棵树T为最小割树，如果对于树上的所有边(s,t)，树上去掉(s,t)后产生的两个集合恰好是原图上(s,t)的最小割把原图分成的两个集合，且边(u,v)的权值等于原图上(u,v)的最小割。最小割树的性质：原图上u,v两点最小割就是最小割树上u到v的路径上权值最小的边。 ...

2019-12-27

0 1075

[CQOI2016]不同的最小割

题目描述学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 s,ts,t 不在同一个部分中，则称这个划分是关于 s,ts,t 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 s,ts,t 的最小割指的是...

2019-12-27

0 405

[ZJOI2011]最小割

题目描述小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： ”对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容...

2019-12-27

0 549