ACM-ICPC 2018 徐州赛区网络预赛 J Maze Designer（最大生成树+LCA）-白红宇

ACM-ICPC 2018 徐州赛区网络预赛 J Maze Designer（最大生成树+LCA）

阅读量：6819 次

发布时间：2019-06-26

本文共 3212 字，大约阅读时间需要 10 分钟。

题意

一个N*M的矩形,每个格点到其邻近点的边有其权值,需要构建出一个迷宫,使得构建迷宫的边权之和最小,之后Q次查询,每次给出两点坐标,给出两点之间的最短路径

分析

可以把每个格点视作视作图的点,隔开两点的边视作图的边,则构建迷宫可以视作求其生成树,剩余的边就是组成迷宫的墙.因为要花费最小,所以使删去的墙权置最大即可,呢么就是求最大生成树即可.

然后每次查询相当于查这个最大生成树上任意两点的最短距离,到这一步就是个LCA了。

这题码量不少，还好队友给力。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #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
                   
                    //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\n", L.dist[L.ask[i].u] + L.dist[L.ask[i].v] - 2 * L.dist[L.ask[i].lca]); } }}

转载于:https://www.cnblogs.com/fht-litost/p/9668666.html

你可能感兴趣的文章

移植Modbus到STM32F103（4）：串口数据长度和校验的支持