专栏文章

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

WWild_Of_The_World
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipzvctd
此快照首次捕获于
2025/12/03 20:39
3 个月前
此快照最后确认于
2025/12/03 20:39
3 个月前
查看原文
  • 优先队列退空栈会有问题，栈的大小会变得特别大，但不会报错
问题MAX太小，1《7=128，可用INT_MAX替代自己定义
CPP
#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：
CPP
#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;
}
黄毛
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...