P1967 [NOIP2013 提高组] 货车运输 kruscal+树上倍增 求调

Question

P1967 [NOIP2013 提高组] 货车运输

求调!

欢迎非AI回答!

不欢迎借鉴GPT的回答!

Code:

#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;

#define N 1005
#define int long long
#define inf 9e18
#define min(a,b) (a<b?a:b)

int n,m;
vector<pair<int,int> >map[N],tree[N];
int root[N],depth[N];
pair<int,int>fa[N][15];

inline int find(int v)
{
    if(root[v]==v)
        return v;
    return root[v]=find(root[v]);
}

inline void Union(int x,int y){root[find(x)]=find(y);}

vector<pair<int,pair<int,int> > >edge;
void kruskal()
{
    for(int i=1;i<=n;++i)
        root[i]=i;
    for(int i=1;i<=n;++i)
        for(auto j:map[i])
            edge.push_back({j.second,{i,j.first}});
    sort(edge.begin(),edge.end(),greater<pair<int,pair<int,int> > >());
    for(int i=1;i<=m;++i)
    {
        auto Edge=edge[i];
        if(find(Edge.second.first)!=find(Edge.second.second))
        {
            Union(Edge.second.first,Edge.second.second);
            tree[Edge.second.first].push_back({Edge.second.second,Edge.first});
            tree[Edge.second.second].push_back({Edge.second.first,Edge.first});
        }
    }
}

void init(int i,int father,int w)
{
    fa[i][0].first=father;
    fa[i][0].second=w;
    depth[i]=depth[father]+1;
    for(int j=1;j<15;++j)
        fa[i][j].first=fa[fa[i][j-1].first][j-1].first,
        fa[i][j].second=min(fa[i][j-1].second,fa[fa[i][j-1].first][j-1].second);
    for(auto j:tree[i])
        if(j.first!=father)
            init(j.first,i,j.second);
}

int len(int x,int y)
{
    if(!(find(x)&&find(y))||find(x)!=find(y))
        return -1;
    if(depth[x]<depth[y])
        swap(x,y);
    int ans=inf;
    for(int i=0,j=depth[x]-depth[y];(1<<i)<=j;++i)
        if((1<<i)&j)
            ans=min(ans,fa[x][i].second),
            x=fa[x][i].first;
    if(x==y)
        return ans;
    for(int i=14;i>=0;--i)
        if(fa[x][i].first!=fa[y][i].first)
            ans=min(ans,min(fa[x][i].second,fa[y][i].second)),
            x=fa[x][i].first,
            y=fa[y][i].first;
    return min(ans,min(fa[x][0].second,fa[y][0].second));
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y,w;
        scanf("%lld%lld%lld",&x,&y,&w);
        map[x].push_back({y,w});
        map[y].push_back({x,w});
    }
    kruskal();
    bool flag[N]={};
    for(int i=1;i<=n;++i)
        if(!flag[find(i)])
            init(find(i),0,0),
            flag[find(i)]=1;
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        int x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld\n",len(x,y));
    }
    return 0;
}

Answer 1

问题已解决

AC记录