https://nanti.jisuanke.com/t/31462
题意
一个N*M的矩形,每个格点到其邻近点的边有其权值,需要构建出一个迷宫,使得构建迷宫的边权之和最小,之后Q次查询,每次给出两点坐标,给出两点之间的最短路径
分析
可以把每个格点视作视作图的点,隔开两点的边视作图的边,则构建迷宫可以视作求其生成树,剩余的边就是组成迷宫的墙.因为要花费最小,所以使删去的墙权置最大即可,呢么就是求最大生成树即可.
然后每次查询相当于查这个最大生成树上任意两点的最短距离,到这一步就是个LCA了。
这题码量不少，还好队友给力。
#include <iostream> #include <vector> #include <cstdio> #include <string> #include <cstring> #include <map> #include <algorithm> #include <queue> #include <set> #include <cmath> #include <sstream> #include <stack> #include <fstream> #include <ctime> #pragma warning(disable:4996); #define mem(sx,sy) memset(sx,sy,sizeof(sx)) typedef long long ll; typedef unsigned long long ull; const double eps = 1e-8; const double PI = acos(-1.0); const ll llINF = 0x3f3f3f3f3f3f3f3f; const int INF = 0x3f3f3f3f; using namespace std; //#define pa pair<int, int> //const int mod = 1e9 + 7; const int maxn = 1000005; const int maxq = 300005; struct node { int u, v, w, next, lca; }; struct LCA { node edges[maxn], ask[maxq]; int ghead[maxn], gcnt, ahead[maxn], acnt; int anc[maxn]; int vis[maxn]; ll dist[maxn]; int fa[maxn]; void addedge(int u, int v, int w) { edges[gcnt].v = v; edges[gcnt].w = w; edges[gcnt].next = ghead[u]; ghead[u] = gcnt++; } void addask(int u, int v) { ask[acnt].u = u; ask[acnt].v = v; ask[acnt].next = ahead[u]; ahead[u] = acnt++; } void init() { mem(vis, 0); mem(ghead, -1); mem(ahead, -1); gcnt = 0; acnt = 0; } int Find(int x) { return fa[x] == x ? x : (fa[x] = Find(fa[x])); } void getLCA(int u, int d) { dist[u] = d; fa[u] = u; vis[u] = 1; for (int i = ghead[u]; i != -1; i = edges[i].next) { int v = edges[i].v; if (!vis[v]) { getLCA(v, d + edges[i].w); fa[v] = u; anc[fa[v]] = u; } } for (int i = ahead[u]; i != -1; i = ask[i].next) { int v = ask[i].v; if (vis[v]) ask[i].lca = ask[i ^ 1].lca = Find(ask[i].v); } } }L; struct edge { int u, v; ll w; bool operator<(const edge &e)const { return w>e.w; } edge(int _u = 0, int _v = 0, ll _w = 0) :u(_u), v(_v), w(_w) {} }; struct Kruskal { int n, m; edge edges[maxn]; int fa[maxn]; int Find(int x) { return fa[x] == -1 ? x : fa[x] = Find(fa[x]); } void init(int _n) { this->n = _n; m = 0; mem(fa, -1); } void AddEdge(int u, int v, ll dist) { edges[m++] = edge(u, v, dist); } ll kruskal() { ll sum = 0; int cntnum = 0; sort(edges, edges + m); for (int i = 0; i < m; i++) { int u = edges[i].u, v = edges[i].v; if (Find(u) != Find(v)) { L.addedge(u, v, 1); L.addedge(v, u, 1); //cout << u << " " << v << endl; sum += edges[i].w; fa[Find(u)] = Find(v); if (++cntnum >= n - 1) return sum; } } return -1; } }G; int main() { int n, m; while (~scanf("%d%d", &n, &m)) { G.init(n*m); L.init(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int w1, w2; char c1, c2; scanf(" %c%d %c%d", &c1, &w1, &c2, &w2); if (c1 == 'D') { G.AddEdge((i - 1)*m + j, i*m + j, w1); } if (c2 == 'R') { G.AddEdge((i - 1)*m + j, (i - 1)*m + j + 1, w2); } } } G.kruskal(); int q; scanf("%d", &q); for (int i = 1, x1, x2, y1, y2; i <= q; i++) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); int u = (x1 - 1)*m + y1; int v = (x2 - 1)*m + y2; L.addask(u, v); L.addask(v, u); } L.getLCA(1, 0); for (int i = 0; i < L.acnt; i += 2) { printf("%lld ", L.dist[L.ask[i].u] + L.dist[L.ask[i].v] - 2 * L.dist[L.ask[i].lca]); } } }