【模板】ISAP – 最大流

ISAP卡常成功 🙂

72ms—>60ms

实测BFS会造成玄学优化

 

2+

Vizing定理

Vizing定理:任意(简单, 无向)图\( G \)的边着色数 (edge chromatic number,\( χ′(G)) \)等于\( Δ(G) \)或\( Δ(G) + 1\),其中\( Δ(G) \)指图\( G \)中最大的度。

由Vizing定理可知\(χ'(G)=Δ(G) \)或\( Δ(G) + 1\)。若为前者,称\(G\)为第一类图(Class 1),否则称为第二类图 (Class 2)。虽然只有两类,但Holyer (1981)证明了,确定任意图属于哪一类是一个NP完全问题。

不过,对于特定类型的图也有部分的解答。比如对于简单平面图,Vizing (1965)自己证明了,如果\(Δ(G)≥8 \)则是第一类的,但对于\(Δ(G)=2,3,4,5 \)的情况则有第二类图存在:把正多面体的其中一边截成两条,即可得到 \(Δ(G)=3,4,5 \)的平面图,他们是第二类的;而任何长度是奇数的圈(比如三角形)就是\( Δ(G)=2 \)的第二类图。对于剩下的两种情况,Vizing提出了猜想:

平面图Vizing猜想:
※任何简单平面图如果\( Δ(G)≥6 \)(或\(7\)),则是第一类的。(Vizing 1965)

在\( Δ(G)≥7 \)的情形,Sanders & Zhao (2001) 给出了肯定的结果。因此只剩下\( Δ(G)≥6 \)的情形尚待解决。

0

Tarjan求有向图强连通分量【模板】

0

倍增求LCA【模板】

倍增求LCA

0

1030总结

T1

这一题太水了,然而还是写错了 TwT 以后要认真读题

T2

答案是

\[ \frac { \left[ \sum _ { i = 1 } ^ {  { k } } \sum _ { j = 1 } ^ {  { k } } \operatorname { dis } \left( d _ { i } , d _ { j } \right) \right] \times ( k – 1 ) ! } { k ! }\]

然后\( O(n)\)树形dp即可

T3

考虑从每个点向外出发,状压一个\(S\)表示\(4P+1 \sim 4P+3\)步走到的点。
然后bfs即可。
检验某个点是否被覆盖\(k\)次,如果是则符合题意。
\(O(k(n+m))\),实际上还要带个常数\(16\)

0

[JZOJ4735]最小圈

Problem

对于一张有向图,要你求图中最小圈的平均值最小是多少,即若一个圈经过k个节点,那么一个圈的平均值为圈上k条边权的和除以k,现要求其中的最小值
输出一行一个数,表示最小圈的值。你的答案被视为正确当且仅当与标准答案的绝对误差不超过1e-5
\(n \leq 3000, m \leq 10000, |W_{i,j}|\leq 10^5 , W_{i,j}\)表示边权,是实数

0

[JZOJ4722]跳楼机

Problem

DJL为了避免成为一只咸鱼,来找srwudi学习压代码的技巧。
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多,srwudi改造了一个跳楼机,使得访客可以更方便的上楼。
经过改造,srwudi的跳楼机可以采用以下四种方式移动:
1、向上移动x层;
2、向上移动y层;
3、向上移动z层;
4、回到第一层。
一个月黑风高的大中午,DJL来到了srwudi的家,现在他在srwudi家的第一层,碰巧跳楼机也在第一层。DJL想知道,他可以乘坐跳楼机前往的楼层数。

对于20%的数据,\(1≤h, x, y, z≤100\);
对于40%的数据,\(1≤h, x, y, z≤10^5\);
对于100%的数据,\(1≤h≤10^{18},1≤x, y, z≤10^5\)。

0

最小瓶颈路

最小瓶颈路问题是指在一张无向图中,询问一个点对(u,v),需要找出从u到v的一条简单路径,使路径上所有边中最大值最小。

定理:无向图中,任意两个结点的最小瓶颈路肯定在最小生成树上。

0

可行性遍历问题简介之Hamilton回路

可行遍历问题是一个很实际的问题:按一定顺序走遍图的所有顶点或者所有边。具体来说可以分为如下四个问题:

  • Hamilton回路问题 是否可以从某点出发顺着边走,每个点恰好走一次以后回到出发点?
  • Euler回路问题 是否可以从某点出发顺着边走,每条边恰好走一次以后回到出发点?
  • 旅行商问题(ISP) 如果每个边上的权值不同,那么在所有Hamilton回路中求出权值和最小的那一条.
  • 中国邮递员问题 如果不存在Euler回路,怎样才能在每条边至少走过一次后回到出发点,并使回路上权值和尽量小?
0

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部