「Bzoj 1576」「Usaco2009 Jan」安全路经 (最短路树 + 并查集 + 贪心)

BZOJ 1576
题意:给定一张$n$点$m$边无向图,请你找出$1 \to n$不经过$1 \to n$的最短路的最后一条边的最短路。保证最短路唯一

保证最短路唯一,那么构造最短路树。
接着最短路树上就是最短路,考虑非树边才能得到答案。
对于每条非树边$u,v$,他加入树就形成了环,这个环$u,v$上所有点(除了$\text{LCA}(u,v)$)都可以得到一个新的路径长,即为$dis(u)+dis(v)+W_{u,v}-dis(i)$,发现这个答案只与这条边有关,所以我们可以直接按这个排序,然后从小到大枚举非树边$u,v$,更新环上没更新的点。

这里可以树剖+线段树维护,但是有最方便的方法:
没更新的点更新明显是一个合并的过程,用并查集维护即可。类似倍增跳LCA/树剖的方法来合并

知识点
保证最短路唯一:最短路树
并查集妙用
不要开小关于边的数组

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;
    int cnt, n, lk[MAXN], vis[MAXN], flk[MAXN];
    vector<int> G[MAXN];

    bool hungary(int u) {
        for (int i = 0; i < (int)G[u].size(); i++) {//枚举每个右边的点匹配 
            int v = G[u][i];
            if (vis[v] != cnt) {//尝试修改过的节点就不需要遍历了
                vis[v] = cnt;
                if (!lk[v] || hungary(lk[v])) {
                    lk[v] = u, flk[u] = v;
                    return true;//成功匹配 
                }
            }
        }
        return false;
    }
    void clean() {}
    int solve() {

        clean();
        cin >> n;
        for (int d, i = 0; i < n; ++i) {
            scanf("%d", &d);
            int t1 = (i + d) % n + 1;
            int t2 = ((i - d) % n + n) % n + 1;
            if (t1 > t2) swap(t1, t2);
            G[i + 1].push_back(t1 + n), G[i + 1].push_back(t2 + n);
        }

        int ans = 0;
        for (int i = n; i >= 1; --i) 
            ans += hungary(cnt = i);

        if (ans != n) return puts("No Answer");

        for (int i = 1; i <= n; ++i) printf("%d ", flk[i] - n - 1);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

搬运自 NOI 2009 变换序列 - BYVoid
算法证明
实现简单的方法往往证明并不容易,该算法运用了贪心的思想。首先我们可以发现,有一些可以直接确定的匹配,这些就是度为1的顶点,必须与其唯一的对应点对应。样例如图2所示,(1,2),(4,3)一定存在于任意一个解中(如果有解的话)。这样的话,我们就可以把已经确定的顶点去除,删除后如果又发现了剩余度为1的顶点,那么继续去除,直到不存在为止。
剩下的顶点中,X集合顶点个数一定与Y集合顶点个数相等。X集合每个顶点的度都是2,所以Y集合中的所有顶点度也都是2。于是剩下的顶点构成了若干个互不连同的环,每个顶点属于且只属于一个环,我们只需在此图上求字典序最小的匹配即可。每个环的匹配只有两种方式,如果我们从环上X集合中序号最小的顶点贪心的选择与序号较小的点匹配,那么该环上的匹配就是字典序最小。样例如图3。
由于事先不知道那些顶点在环上,哪些可以直接确定。从X集合每个顶点倒序查找增广路,就可以保证最后的最优,也就是字典序尽量小。因为如果一个顶点在环上,找到的一定是环上较优的匹配方式,而不在环上的点也可以被后来的增广而修正。

图2
Markdown
图3
Markdown

解法4 贪心
算法描述
按照解法3证明中的描述,我们可以预处理所有已经确定的匹配,并在图中删去。对于剩下的每个环,只需从序号最小的点开始深度优先搜索,并进行匹配即可。
算法证明
证明同解法3。

------ 本文结束 ------