Loading... ## 图论 <!--more--> --- ### Boruvka算法求最小生成树 - 每次对每个当前的连通分量都找到连出的最短边，尝试 一同加入。 - 此算法的正确性证明与Prim 算法类似，可以看作并行 的Prim. - 而且更好的性质是，如果这些最短边两两不同，一定是 - 可以加入的（若有环，环上最大边根本不会被选！）。 加入完后新一轮缩点即可。 - 边权相同的情况用一些方法破环，比如权相同时选序号 最小的。 - 期望复杂度线性，优于普通Prim、堆优化Prim、Kruskal（注意是大大优于Kruskal，因为Kruskal 瓶颈是排序而不是并查集，后者可视作线性）。 - 最坏复杂度与Kruskal 同阶。 --- ### k短路，k小生成树 - 以上理论算法的拓展较多，如次小生成树、次短路乃至 更一般的k 短路、k 小生成树，这方面可以详见俞鼎力的国家集训队论文，有比较系统的整理。 --- ### 经典题型 #### 2-SAT - 婚礼问题 n对未婚夫妻想举行婚礼，每对有两个可供选择的时间，一个司仪能否参与所有婚礼？ - 本题甚至不需要利用时间的连续性质，直接把这道特殊 题转化为一般情况，任意给定每两对夫妻的两个时段的冲突情况也可解决。 - 每一对未婚夫妻拆点，不妨记为i1 和i2，那么i1 和j1 冲突就意味着i1 必选j2，j1 必选i2，因此由i1 向j2 连边，j1 向i2 连边。 - 每对必须选且仅选一个，且选了一个点必须选它的后继。 - 容易想到按照拓扑序贪心，但为了得到拓扑序必须先求 强连通分量缩点。 - 若某对夫妻的两点在同一个强连通分量中显然无解。 逆拓扑序选点即可，每选一个点立刻删除该对夫妻另一 个点，并递归删除前驱。 - 由于原图的对称性，缩点后仍然对称，因此这种贪心的 正确性易证。 ```cpp #include<bits/stdc++.h> using namespace std; int n, m; struct Edge{ int to, nxt; }e[4000009]; int head[2000009], tot; int dfn[2000009], low[2000009], Time, color[2000009], group; bool vis[2000009]; void add(int x, int y){ e[++tot].to = y; e[tot].nxt = head[x]; head[x] = tot; } stack<int> st; void tarjan(int x){ low[x] = dfn[x] = ++Time; vis[x] = 1; st.push(x); for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; if(!dfn[y]){ tarjan(y); low[x] = min(low[x], low[y]); } else if(vis[y]){ low[x] = min(low[x], dfn[y]); } } if(dfn[x] == low[x]){ group++; while(st.top() != x && !st.empty()){ int q = st.top(); st.pop(); color[q] = group; vis[q] = 0; } color[st.top()] = group; vis[x] = 0; st.pop(); } } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ int x, xv, y, yv; scanf("%d%d%d%d", &x, &xv, &y, &yv); add(x + !xv * n, y + yv * n); add(y + !yv * n, x + xv * n); } for(int i = 1; i <= 2 * n; i++){ if(!dfn[i]) tarjan(i); } for(int i = 1; i <= n; i++){ if(color[i] == color[i + n]){ printf("IMPOSSIBLE\n"); return 0; } } printf("POSSIBLE\n"); for(int i = 1; i <= n; i++){ printf("%d ", color[i] > color[i + n]); } return 0; } ``` --- #### 带锁最短路 - 钥匙路径 图的一些边上有锁，共有k 类锁（k 非常小，10 以内），一些边上有钥匙，每种钥匙对应一种锁，求最短路。 - 显然手上的钥匙不同能走的路径截然不同，应该把不同的手上钥匙状态视为不同状态。 - 用d[i][j] 表示钥匙状态为j 时走到点i 的最短距离，j 需要记录所有种类钥匙的有无。 - 此类问题容易遇到转移顺序的问题，所幸本题中钥匙只可能越来越多不可能变少，按钥匙数从少到多处理当前钥匙状态到所有点的距离即可，相同钥匙数更新顺序任意，注意计算时不仅要更新本层还要给钥匙数更多的状态提前更新“初始值”。 Last modification：January 27, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏