Gym 100851 Distance on Triangulation

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：给你一个N边形，然后这个n边形有n-3条边，然后询问2点之间的最短路。

题解：分治。

我们可以找到一条边，使得这幅图能分成大小相同的2幅图，那么我们就可以确定那些被分割开的询问的答案是多少了。

我们假定u v是分开的，然后我们从u点bfs一遍现在的图，v点bfs一遍现在的图，确定所有点离这2个点的位置，对于切断的询问更新答案。

需要注意的就是，每次都一定要重新建图，免得遍历太多的没有用的边。

递归结束的时候是这幅图只有3个点了，如果在3个点中的最短路，那么一定是1，假定2点不重合。

代码1：离线写法

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("distance.in","r",stdin); freopen("distance.out","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

struct Node{

    int u, v, id;

};

vector<int> vc[N][], ee[N];

vector<pll> e[N][];

vector<Node> q[N][];

int ans[N], pos[N], num[N];

int lf[N], rt[N], ok[N];

int d[N][];

queue<int> que;

void bfs(int b, int id){

    d[b][id] = ;

    que.push(b);

    while(!que.empty()){

        int u = que.front();

        que.pop();

        for(auto v : ee[u]){

            if(d[v][id] > d[u][id]+){

                d[v][id] = d[u][id]+;

                que.push(v);

            }

        }

    }

}

void solve(int k, int op){

    if(vc[k][op].size() <=  || q[k][op].size() == ) return ;

    int nodes = vc[k][op].size();

    for(int i = ; i < nodes; ++i){

        ee[i].clear();

        pos[vc[k][op][i]] = i;

        d[i][] = d[i][] = inf;

        ee[i].pb((i+)%nodes);

        ee[i].pb((i-+nodes)%nodes);

    }

    int Max = inf, id = ;

    for(int i = ; i < e[k][op].size(); ++i){

        int u = e[k][op][i].fi, v = e[k][op][i].se;

        int tmp = max(pos[v]-pos[u], nodes - pos[v]+pos[u]);

        if(tmp < Max) {

            Max = tmp;

            id = i;

        }

        ee[pos[u]].pb( pos[v]);

        ee[pos[v]].pb( pos[u]);

    }

    vc[k+][].clear(); vc[k+][].clear();

    q[k+][].clear(); q[k+][].clear();

    e[k+][].clear(); e[k+][].clear();

    int tu = e[k][op][id].fi, tv = e[k][op][id].se;

    for(int i = ; i < nodes; ++i){

        if(vc[k][op][i] == tu || vc[k][op][i] == tv){

            vc[k+][].pb(vc[k][op][i]);

            vc[k+][].pb(vc[k][op][i]);

        }

        else if(vc[k][op][i] < tu || vc[k][op][i] > tv)

            vc[k+][].pb(vc[k][op][i]), lf[vc[k][op][i]] = ;

        else

            vc[k+][].pb(vc[k][op][i]), rt[vc[k][op][i]] = ;

    }

    bfs(pos[tu], );

    bfs(pos[tv], );

    for(int i = , u, v; i < e[k][op].size(); ++i){

        u = e[k][op][i].fi, v = e[k][op][i].se;

        if(lf[u] || lf[v]) e[k+][].pb(e[k][op][i]);

        else if(rt[u] || rt[v]) e[k+][].pb(e[k][op][i]);

    }

    for(int i = , u, v, aid; i < q[k][op].size(); ++i){

        u = q[k][op][i].u, v = q[k][op][i].v, aid = q[k][op][i].id;

        if(lf[u] && lf[v]) {

            q[k+][].pb(q[k][op][i]);

            continue;

        }

        else if(rt[u] && rt[v]){

            q[k+][].pb(q[k][op][i]);

            continue;

        }

        u = pos[u], v = pos[v];

        ans[aid] = min(d[u][]+d[v][], d[u][] + d[v][]);

    }

    for(auto v : vc[k][op]){

        lf[v] = rt[v] = ;

        ok[v] = ;

    }

    solve(k+, );

    solve(k+, );

}

int main(){

    Fopen;

    int n, m, u, v;

    scanf("%d", &n);

    for(int i = ; i <= n; ++i){

        vc[][].pb(i);

    }

    for(int i = ; i <= n - ; ++i){

        scanf("%d%d", &u, &v);

        if(u > v) swap(u,v);

        e[][].pb({u,v});

    }

    scanf("%d", &m);

    for(int i = ; i <= m; ++i){

        scanf("%d%d", &u, &v);

        if(u > v) swap(u,v);

        if(u == v)

            continue;

        q[][].pb({u,v,i});

    }

    solve(,);

    for(int i = ; i <= m; ++i){

        printf("%d\n", ans[i]);

    }

    return ;

}

离线看着麻烦其实还是挺简单的。

代码2：在线写法

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("distance.in","r",stdin); freopen("distance.out","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL mod =  (int)1e9+;

const int N = 5e4+;

vector<int> ee[N];

int pos[N], que[N];

struct Node{

    vector<int> v, d[];

    vector<pll> e;

    int mn, mx, nodes;

    Node * lson, * rson;

    void bfs(int b,int id){

        d[id][b] = ;

        int l = , r = ;

        que[l] = b;

        while(l < r){

            int u = que[l++];

            for(auto v : ee[u]){

                if(d[id][v] > d[id][u]+){

                    d[id][v] = d[id][u]+;

                    que[r++] = v;

                }

            }

        }

    }

    void solve(){

        nodes = v.size();

        if(nodes <= ) return ;

        for(int i = ; i < nodes; ++i){

            pos[v[i]] = i;

            d[].pb(inf); d[].pb(inf);

            ee[i].clear();

            ee[i].pb((i+)%nodes);

            ee[i].pb((i+nodes-)%nodes);

        }

        int Max = inf, id = ;

        for(int i = ; i < nodes-; ++i){\

            int x = pos[e[i].fi], y = pos[e[i].se];

            int tmp = max(y-x, nodes-(y-x));

            if(tmp < Max) {

                Max = tmp;

                id = i;

            }

            ee[x].pb(y);

            ee[y].pb(x);

        }

        mn = e[id].fi, mx = e[id].se;

        lson = new Node; rson = new Node;

        for(int i = ; i < nodes; ++i){

            if(v[i] >= mn && v[i] <= mx) lson -> v.pb(v[i]);

            if(v[i] <= mn || v[i] >= mx) rson -> v.pb(v[i]);

        }

        bfs(pos[mn], );

        bfs(pos[mx], );

        for(int i = ; i < nodes-; ++i){

            int x = e[i].fi, y = e[i].se;

            if((x > mn && x < mx) || (y > mn && y < mx)) lson -> e.pb(e[i]);

            if(x < mn || y < mn || x > mx || y > mx) rson -> e.pb(e[i]);

        }

        lson -> solve();

        rson -> solve();

    }

    int Query(int x, int y){

        if(nodes <= ) return ;

        if((x > mn && x < mx) && (y > mn && y < mx)) return lson -> Query(x,y);

        if((x < mn || x > mx) && (y < mn || y > mx)) return rson -> Query(x,y);

        x = lower_bound(v.begin(), v.end(), x) - v.begin();

        y = lower_bound(v.begin(), v.end(), y) - v.begin();

        return min(d[][x]+d[][y], d[][x]+d[][y]);

    }

}rt;

int main(){

    Fopen;

    int n, m, u, v;

    scanf("%d", &n);

    for(int i = ; i <= n; ++i){

        rt.v.pb(i);

    }

    for(int i = ; i <= n - ; ++i){

        scanf("%d%d", &u, &v);

        if(u > v) swap(u,v);

        rt.e.pb({u,v});

    }

    rt.solve();

    scanf("%d", &m);

    while(m--){

        scanf("%d%d", &u, &v);

        int ans = ;

        if(u != v) ans = rt.Query(u,v);

        printf("%d\n", ans);

    }

    return ;

}

在线写法要确定询问的点是不是都在一副新的图上，是就继续往下递归，否就在这个地方询问。

这题目中在线比离线的慢一点点。

因为在线写法的询问是严格的lg(n)是一个固定值，因为每次往下走，你就会使得二分的长度/2，就相当于是二分了一次了。。。。。

然后我又写了一个bug，疯狂TLE，惊了。

int Max = inf, id = ;

    for(int i = ; i < e[k][op].size(); ++i){

        int u = e[k][op][i].fi, v = e[k][op][i].se;

        int tmp = max(pos[v]-pos[u], nodes - pos[v]+pos[u]);

        if(tmp < Max) {

           tmp = Max;

            id = i;

        }

        ee[pos[u]].pb( pos[v]);

        ee[pos[v]].pb( pos[u]);

}

看着没什么问题。。。实际上问题大了。

应该是 Max = tmp。。。这样加多了递归的层数，然后会加多存的东西，会导致TLE和MLE。

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("distance.in","r",stdin); freopen("distance.out","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

struct Node{

    int u, v, id;

};

vector<int> vc[N][], ee[N];

vector<pll> e[N][];

vector<Node> q[N][];

int ans[N], pos[N], num[N];

int lf[N], rt[N], ok[N];

int d[N][];

queue<int> que;

void bfs(int b, int id){

    d[b][id] = ;

    que.push(b);

    while(!que.empty()){

        int u = que.front();

        que.pop();

        for(auto v : ee[u]){

            if(ok[v] && d[v][id] > d[u][id]+){

                d[v][id] = d[u][id]+;

                que.push(v);

            }

        }

    }

}

void solve(int k, int op){

    if(vc[k][op].size() <=  || q[k][op].size() == ) return ;

    for(int i = ; i < vc[k][op].size(); ++i){

        pos[vc[k][op][i]] = i;

        d[vc[k][op][i]][] = d[vc[k][op][i]][] = inf;

        ok[vc[k][op][i]] = ;

    }

    int Max = inf, id = , totnum = vc[k][op].size();

    for(int i = ; i < e[k][op].size(); ++i){

        int u = e[k][op][i].fi, v = e[k][op][i].se;

        int tmp = max(pos[v]-pos[u]-, totnum - (pos[v]-pos[u]-) - );

        if(tmp < Max) {

            tmp = Max;

            id = i;

        }

    }

    vc[k+][].clear(); vc[k+][].clear();

    vc[k+][].shrink_to_fit(); vc[k+][].shrink_to_fit();

    q[k+][].clear(); q[k+][].clear();

    q[k+][].shrink_to_fit(); q[k+][].shrink_to_fit();

    e[k+][].clear();e[k+][].clear();

    e[k+][].shrink_to_fit(); e[k+][].shrink_to_fit();

    int tu = e[k][op][id].fi, tv = e[k][op][id].se;

    for(int i = ; i < totnum; ++i){

        if(vc[k][op][i] == tu || vc[k][op][i] == tv){

            vc[k+][].pb(vc[k][op][i]);

            vc[k+][].pb(vc[k][op][i]);

        }

        else if(vc[k][op][i] < tu || vc[k][op][i] > tv)

            vc[k+][].pb(vc[k][op][i]), lf[vc[k][op][i]] = ;

        else

            vc[k+][].pb(vc[k][op][i]), rt[vc[k][op][i]] = ;

    }

    bfs(tu,);

    bfs(tv,);

    for(int i = , u, v; i < e[k][op].size(); ++i){

        u = e[k][op][i].fi, v = e[k][op][i].se;

        if(lf[u] || lf[v]) e[k+][].pb(e[k][op][i]);

        else if(rt[u] || rt[v]) e[k+][].pb(e[k][op][i]);

    }

    for(int i = , u, v, aid; i < q[k][op].size(); ++i){

        u = q[k][op][i].u, v = q[k][op][i].v, aid = q[k][op][i].id;

        if(lf[u] && lf[v]) {

            q[k+][].pb(q[k][op][i]);

            continue;

        }

        else if(rt[u] && rt[v]){

            q[k+][].pb(q[k][op][i]);

            continue;

        }

        ans[aid] = min(ans[aid], d[u][]+d[v][]);

        ans[aid] = min(ans[aid], d[u][]+d[v][]);

    }

    for(auto v : vc[k][op]){

        lf[v] = rt[v] = ;

        ok[v] = ;

    }

    vc[k][op].clear();

    vc[k][op].shrink_to_fit();

    e[k][op].clear();

    e[k][op].shrink_to_fit();

    q[k][op].clear();

    q[k][op].shrink_to_fit();

    solve(k+, );

    solve(k+, );

}

int main(){

    Fopen;

    int n, m, u, v;

    scanf("%d", &n);

    for(int i = ; i < n; ++i){

        vc[][].pb(i);

        ee[i].pb(i+);

        ee[i+].pb(i);

    }

    vc[][].pb(n);

    ee[].pb(n); ee[n].pb();

    for(int i = ; i <= n - ; ++i){

        scanf("%d%d", &u, &v);

        if(u > v) swap(u,v);

        e[][].pb({u,v});

        ee[u].pb(v);

        ee[v].pb(u);

    }

    scanf("%d", &m);

    memset(ans, inf, sizeof ans);

    for(int i = ; i <= m; ++i){

        scanf("%d%d", &u, &v);

        if(u > v) swap(u,v);

        if(u == v) {

            ans[i] = ;

            continue;

        }

        q[][].pb({u,v,i});

    }

    solve(,);

    for(int i = ; i <= m; ++i){

        printf("%d\n", ans[i]);

    }

    return ;

}