P1967 [NOIP 2013 提高组] 货车运输

Wild_Of_The_World · 2025-03-07 22:10:48 · 个人记录

• 优先队列退空栈会有问题，栈的大小会变得特别大，但不会报错

问题MAX太小，1《7=128，可用INT_MAX替代自己定义

#include<bits/stdc++.h>
using namespace std;
const int N=5e4;
const int MAX=1<<7;
int n,m,q;
struct Edge{
    int u,v,w;
    bool operator<(Edge b)const{return this->w<b.w;}
};
int fa[N];
int find(int x){
    if(fa[x]!=x) return fa[x]=find(fa[x]);
    return x;
}
int head[N],nxt[N],to[N],value[N],cnt;
void add(int u,int v,int w){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    value[cnt]=w;
    return;
}
int deep[N],_fa[N][25],dist[N][25];
void dfs1(int x,int father,int v){
    deep[x]=deep[father]+1;
    _fa[x][0]=father;
    dist[x][0]=v;
    for(int i=1;(1<<i)<=deep[x];i++){
        _fa[x][i]=_fa[_fa[x][i-1]][i-1];
        dist[x][i]=min(dist[x][i-1],dist[_fa[x][i-1]][i-1]);
    }
    for(int i=head[x];i;i=nxt[i])   if(to[i]!=father)   dfs1(to[i],x,value[i]);
    return ;
}
int lca(int a,int b){
    int ans=MAX;
    if(deep[a]<deep[b]) swap(a,b);
    for(int i=20;i>=0;i--) 
        if(deep[_fa[a][i]]>=deep[b]) 
            ans=min(ans,dist[a][i]),a=_fa[a][i];
    if(a==b) return ans;
    for(int i=20;i>=0;i--){
        if(_fa[a][i]!=_fa[b][i]){
            ans=min(ans,dist[a][i]);
            ans=min(ans,dist[b][i]);
            a=_fa[a][i],b=_fa[b][i];
        } 
    }
    return min(ans,min(dist[a][0],dist[b][0]));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("P1967_3.in","r",stdin);
    cin>>n>>m;
    for(int i=0;i<=n;i++) fa[i]=i;
    priority_queue<Edge> Q;
    Edge e;
    for(int i=1;i<=m;i++){
        cin>>e.u>>e.v>>e.w;
        Q.push(e);
    }

    Edge e;
    while(!Q.empty()){
        while(!Q.empty()&&find(Q.top().u)==find(Q.top().v)) Q.pop();
        if(Q.empty()) break;
        e=Q.top();Q.pop();
        int fu=find(e.u),fv=find(e.v);
        fa[fu]=fv;
        add(aim.u,aim.v,aim.w);
        add(aim.v,aim.u,aim.w);
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==i){
            dfs1(i,0,MAX);
            dist[i]=0=MAX;
        }
    }

    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        if(find(a)!=find(b)) cout<<-1<<endl;
        else{
            cout<<lca(a,b)<<endl;
        }
    }
    return 0;
} 

我的100pts：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4;
int n,m,q;
struct Edge{
    int u,v,w;
    bool operator<(Edge b)const{return this->w<b.w;}
};
int fa[N];
int find(int x){
    if(fa[x]!=x) return fa[x]=find(fa[x]);
    return x;
}
int head[N],nxt[N],to[N],value[N],cnt;
void add(int u,int v,int w){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    value[cnt]=w;
    return;
}
int deep[N],_fa[N][25],dist[N][25];
void dfs1(int x,int father,int v){
    deep[x]=deep[father]+1;
    _fa[x][0]=father;
    dist[x][0]=v;
    for(int i=1;(1<<i)<=deep[x];i++){
        _fa[x][i]=_fa[_fa[x][i-1]][i-1];
        dist[x][i]=min(dist[x][i-1],dist[_fa[x][i-1]][i-1]);
    }
    for(int i=head[x];i;i=nxt[i])   
        if(to[i]!=father)   dfs1(to[i],x,value[i]);
    return ;
}
int lca(int a,int b){
    int ans=INT_MAX;
    if(deep[a]<deep[b]) swap(a,b);
    for(int i=20;i>=0;i--) 
        if(deep[_fa[a][i]]>=deep[b]) 
            ans=min(ans,dist[a][i]),a=_fa[a][i];
    if(a==b) return ans;
    for(int i=20;i>=0;i--){
        if(_fa[a][i]!=_fa[b][i]){
            ans=min(ans,dist[a][i]);
            ans=min(ans,dist[b][i]);
            a=_fa[a][i],b=_fa[b][i];
        } 
    }
    return min(ans,min(dist[a][0],dist[b][0]));
}
priority_queue<Edge> Q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  freopen("P1967_3.in","r",stdin);
    cin>>n>>m;
    for(int i=0;i<=n;i++) fa[i]=i;
    Edge e;
    for(int i=1;i<=m;i++){
        cin>>e.u>>e.v>>e.w;
        Q.push(e);
    }

    while(!Q.empty()){
        while(!Q.empty()&&find(Q.top().u)==find(Q.top().v)) 
            Q.pop();
        if(Q.empty()) break;
        Edge e=Q.top();Q.pop();
        int fu=find(e.u),fv=find(e.v);
        fa[fu]=fv;
        add(e.u,e.v,e.w);
        add(e.v,e.u,e.w);
    }
    for(int i=1;i<=n;i++){
        if(find(i)==i){
            dfs1(i,0,INT_MAX);
            dist[i][0]=INT_MAX;
        }
    }

    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        if(find(a)!=find(b)) cout<<-1<<endl;
        else{
            cout<<lca(a,b)<<endl;
        }
    }
    return 0;
} 

黄毛

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int LOG = 20;

int n, m, q;
struct Edge {
    int u, v, w;
    bool operator<(const Edge& b) const { return w < b.w; } // 大顶堆需要运算符返回较小值
};
priority_queue<Edge> Q;

int fa[N];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int head[N], nxt[N], to[N], value[N], cnt;
void add(int u, int v, int w) {
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    value[cnt] = w;
}

int deep[N], _fa[N][LOG], min_edge[N][LOG];
void dfs(int x, int father, int w) {
    deep[x] = deep[father] + 1;
    _fa[x][0] = father;
    min_edge[x][0] = w;
    for (int i = 1; i < LOG; ++i) {
        _fa[x][i] = _fa[_fa[x][i-1]][i-1];
        min_edge[x][i] = min(min_edge[x][i-1], min_edge[_fa[x][i-1]][i-1]);
    }
    for (int i = head[x]; i; i = nxt[i]) {
        if (to[i] != father) {
            dfs(to[i], x, value[i]);
        }
    }
}

int lca(int a, int b) {
    if (deep[a] < deep[b]) swap(a, b);
    for (int i = LOG-1; i >= 0; --i)
        if (deep[_fa[a][i]] >= deep[b])
            a = _fa[a][i];
    if (a == b) return a;
    for (int i = LOG-1; i >= 0; --i)
        if (_fa[a][i] != _fa[b][i])
            a = _fa[a][i], b = _fa[b][i];
    return _fa[a][0];
}

int query_min(int a, int b) {
    int ans = INT_MAX;
    if (deep[a] < deep[b]) swap(a, b);
    for (int i = LOG-1; i >= 0; --i) {
        if (deep[_fa[a][i]] >= deep[b]) {
            ans = min(ans, min_edge[a][i]);
            a = _fa[a][i];
        }
    }
    if (a == b) return ans;
    for (int i = LOG-1; i >= 0; --i) {
        if (_fa[a][i] != _fa[b][i]) {
            ans = min(ans, min(min_edge[a][i], min_edge[b][i]));
            a = _fa[a][i];
            b = _fa[b][i];
        }
    }
    ans = min(ans, min(min_edge[a][0], min_edge[b][0]));
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 0; i < m; ++i) {
        Edge e;
        cin >> e.u >> e.v >> e.w;
        Q.push(e);
    }
    while (!Q.empty()) {
        while (!Q.empty() && find(Q.top().u) == find(Q.top().v))
            Q.pop();
        if (Q.empty()) break;
        Edge e = Q.top(); Q.pop();
        int fu = find(e.u), fv = find(e.v);
        if (fu != fv) {                 //
            fa[fu] = fv;
            add(e.u, e.v, e.w);
            add(e.v, e.u, e.w);
        }                               //
    }
    for (int i = 1; i <= n; ++i) {
        if (find(i) == i) { // 根节点
            dfs(i, 0, INT_MAX);
            min_edge[i][0] = INT_MAX; // 根到虚父节点0的边权设为无穷大
        }
    }
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b))
            cout << "-1\n";
        else
            cout << query_min(a, b) << '\n';
    }
    return 0;
}