[Water]简单图论专题

【图论】

最短路

[生命的绿洲]
@
Dijkstra类最短路维护标号。
@
[过路费]
@
利用Floyd算法,注意到每一层dp的含义是,除了两个端点以外的中间结点的标号不超过k.
事实上,状态为dp[k][i][j]表示中间结点标号不超过k时,ij的最短路径长度。
那么显然.
对于这道题,将点过路费由小到大排序,每完成一层dp更新答案就好了。
(一开始想的分层图,每层做n次Dijkstra,应该可以骗分。。。)
@

无向图的最大团等于补图的最大独立集。

弦图、区间图

图连通性

无向图联通性:
只考虑无向连通图。
『名词:图不联通(至少存在一个点对无路径)』
割点:一个点满足删去后图不联通。
割边(桥):一条边满足删去后图不联通。
点连通度:模最小的点集使得删去后图不联通。
点双连通图:点连通度>1的连通图,不存在割点
边连通度: 模最小的边集使得删去后图不联通。
边双连通图:边连通度>1的连通图,不存在桥。
点双连通分量:极大点双连通子图。
边双连通分量:极大边双连通子图。
Tarjan算法维护:(记录走过的上一条边)
设当前dfs节点为u,另一个节点为v
若v是u搜索树中的儿子,则low[u]=min(low[u],low[v])
若low[v]>=dfn[u],则u是割点
若low[v]>dfn[u],则无向边u->v是桥
否则u->v不在搜索树中,则low[u]=min(low[u],dfn[v])
点(边)双连通分量:见模板
有向图连通性:
有向图的强连通分量:任一点对均互相可达的极大子图。
求法:Tarjan,.
注意利用非树边更新low值时只考虑栈中的点。
缩点后变成DAG,注意重边

最小度限制生成树

@
首先图连通,否则无解。
考虑删除原点的每个连通块,在内部做最小生成树并dfs为有根树。
如果原点的度限制不足以联通这些连通块,则无解。
否则依次贪心地插入最优边,直至K条边用完或是已经解不能更优。

性质填坑:如果当前是原点度数为k的最优解,那么此时再进行一次产生优化的最优变换后一定为原点度数为k+1时的最优解。
@

最小树形图

@
每一次对于每个非原点,找到权值最小的入边,并累加权值和。
如果某个非原点没有入边输出无解。
如果不存在有向环,算法结束,直接退出。
否则将环缩点,对于环上的点的出边点权不变,入边权值减去该点的最小入边权值,构造新图。

这样脑补一下是显然正确的。
@

差分约束系统

[bzoj2330]
@
差分约束裸题。
但是一开始爆栈,又写了非递归。。。
然后又TMD超时。。。
后来发现有一个点是丧心病狂的大环。
于是需要在spfa时将所有的点全部事先入队。。

膜拜到一种用SCC的神做法,貌似这种做法不会被卡。
@

comments powered by Disqus