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-;
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 = ;
const int maxq = ;
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, );
mem(ghead, -);
mem(ahead, -);
gcnt = ;
acnt = ;
} 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] = ;
for (int i = ghead[u]; i != -; 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 != -; i = ask[i].next) {
int v = ask[i].v;
if (vis[v])
ask[i].lca = ask[i ^ ].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 = , int _v = , ll _w = )
:u(_u), v(_v), w(_w) {}
}; struct Kruskal {
int n, m;
edge edges[maxn];
int fa[maxn];
int Find(int x) {
return fa[x] == - ? x : fa[x] = Find(fa[x]);
}
void init(int _n) {
this->n = _n;
m = ;
mem(fa, -);
} void AddEdge(int u, int v, ll dist) {
edges[m++] = edge(u, v, dist);
} ll kruskal() {
ll sum = ;
int cntnum = ;
sort(edges, edges + m);
for (int i = ; i < m; i++) {
int u = edges[i].u, v = edges[i].v;
if (Find(u) != Find(v)) {
L.addedge(u, v, );
L.addedge(v, u, );
//cout << u << " " << v << endl;
sum += edges[i].w;
fa[Find(u)] = Find(v);
if (++cntnum >= n - ) return sum;
}
}
return -;
}
}G; int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
G.init(n*m);
L.init();
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
int w1, w2; char c1, c2;
scanf(" %c%d %c%d", &c1, &w1, &c2, &w2);
if (c1 == 'D') {
G.AddEdge((i - )*m + j, i*m + j, w1);
}
if (c2 == 'R') {
G.AddEdge((i - )*m + j, (i - )*m + j + , w2);
}
}
}
G.kruskal();
int q;
scanf("%d", &q);
for (int i = , x1, x2, y1, y2; i <= q; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int u = (x1 - )*m + y1;
int v = (x2 - )*m + y2;
L.addask(u, v);
L.addask(v, u);
}
L.getLCA(, );
for (int i = ; i < L.acnt; i += ) {
printf("%lld\n", L.dist[L.ask[i].u] + L.dist[L.ask[i].v] - * L.dist[L.ask[i].lca]);
}
}
}