Luogu P1967 貨車運輸

題目描述

A 國有 n 座城市，編号從 1到 n，城市之間有 m 條雙向道路。每一條道路對車輛都有重量限制，簡稱限重。

現在有 q 輛貨車在運輸貨物， 司機們想知道每輛車在不超過車輛限重的情況下，最多能運多重的貨物。

.

輸入格式

第一行有兩個用一個空格隔開的整數 n,m，表示 A 國有 n 座城市和 m 條道路。

接下來 m行每行三個整數 x,y,z，每兩個整數之間用一個空格隔開，表示從 x 号城市到 y号城市有一條限重為 z的道路。

注意： x≠y, 兩座城市之間可能有多條道路 。

接下來一行有一個整數 q，表示有 q 輛貨車需要運貨。

接下來 q 行，每行兩個整數 x,y，之間用一個空格隔開，表示一輛貨車需要從 x 城市運輸貨物到 y 城市，保證 x≠y

.

輸出格式

共有 q行，每行一個整數，表示對于每一輛貨車，它的最大載重是多少。

如果貨車不能到達目的地，輸出 −1。

本題：

kruscal最大生成樹

樹鍊剖分（剖森林！）

并查集（我又寫錯了啊啊啊啊啊）

别的一堆細節細節細節細節細節

代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N = 10005;
int n,m,en,ee,q,fa[N],val[N],head[N];
int father[N],son[N],size[N],depth[N],top[N],seg[N],rev[N];
bool vis[N];						 
struct Bian{
	int from,to,w;
	bool operator <(const Bian &x)const{
		return w<x.w ;
	}
}bian[50005];
struct Edge{
	int next,to,w;
}edge[50005];
priority_queue<Bian> pq;
struct Tree{
	int minn;
}tree[N*4];
int cnt;

int read(){
	int x;
	char ch,last=' ';
	while((ch=getchar())<'0'||ch>'9') last=ch;
	for(x=0;isdigit(ch);ch=getchar())
		x = x*10+ch-'0';
	if(last=='-') x=-x;
	return x;
}

void build(int x,int y,int z){
	bian[++ee].from = x;
	bian[ee].to = y;
	bian[ee].w = z;
}

void add(int x,int y,int l){
	edge[++en].to = y ;
	edge[en].next = head[x];
	head[x] = en;
	edge[en].w = l ;
}

int find(int u){
	if(fa[u]!=u) return fa[u] = find(fa[u]);
	return u;
}

void kruscal(){
	while(!pq.empty()){
	//	cout<<"?"<<endl;
		Bian tmp=pq.top();
		pq.pop();
		int k1=find(tmp.from);
		int k2=find(tmp.to);
		if(k1!=k2) {
	//		++cnt;
//			cout<<tmp.from<<" "<<tmp.to <<endl; 
			fa[k1] = k2;
//			for(int i=1;i<=n;i++)
//				cout<<fa[i]<<" ";
//			cout<<endl;
			add(tmp.from ,tmp.to ,tmp.w );
			add(tmp.to ,tmp.from ,tmp.w );
		}
	}
	//cout<<"cnt="<<cnt<<endl;
}

void dfs1(int u,int f){
//	cout<<u<< ' '<<endl; 
	size[u] = 1;
	depth[u] = depth[f]+1;
	father[u] = f;
	for(int p=head[u];p;p=edge[p].next){
		int v=edge[p].to ;
		if(v==f) continue;
		vis[v] = true;
		dfs1(v,u);
		val[v] = edge[p].w ;
		size[u]+=size[v];
		if(size[son[u]]<size[v]) son[u] = v;
	}
}

void dfs2(int u){
	if(son[u]){
		vis[son[u]] = true;
		top[son[u]] = top[u];
		seg[son[u]] = ++seg[0];
	//	cout<<son[u]<<"seg:"<<seg[0]<<endl;
		rev[seg[0]] = son[u];
		dfs2(son[u]);
	}
	for(int p=head[u];p;p=edge[p].next){
		int v=edge[p].to ;
		if(top[v]) continue;
		vis[v] = true;
		top[v] = v;
		seg[v] = ++seg[0];
		rev[seg[0]] = v;
		dfs2(v); 
	}
}

void create(int rt,int l,int r){
	if(l==r) {
		tree[rt].minn = val[rev[l]];//Rev!!!
		return;
	}
	int mid = (l+r)>>1;
	create(rt<<1,l,mid);
	create(rt<<1|1,mid+1,r);
	tree[rt].minn = min(tree[rt<<1].minn,tree[rt<<1|1].minn);
}

int chaxun(int rt,int l,int r,int x,int y){
	if(x<=l&&r<=y) 	return tree[rt].minn;
	if(r<x||l>y) return 100005;
	int mid = (l+r)>>1;
	return min(chaxun(rt<<1,l,mid,x,y),chaxun(rt<<1|1,mid+1,r,x,y));
}
//
//void tiaoshi(int rt,int l,int r){
//	if(l==r) 	{
//		//cout<<l<<" "<<tree[rt].minn<<endl;
//		return ;	
//	}
//	int mid = (l+r)>>1;
//	tiaoshi(rt<<1,l,mid);
//	tiaoshi(rt<<1|1,mid+1,r);
//}

int query(int u,int v){
	int tmp=100005;
	while(top[u]!=top[v]){
		if(depth[top[u]]<depth[top[v]]) swap(u,v);
	//	cout<<"check "<<top[u]<<" "<<u<<" here"<<endl;
		tmp = min(tmp,chaxun(1,1,n,seg[top[u]],seg[u]));
		u=father[top[u]];
	}
	if(depth[u]>depth[v]) swap(u,v);
//	cout<<"check "<<rev[seg[u]+1]<<" "<<v<<" here"<<endl;
	tmp = min(tmp,chaxun(1,1,n,seg[u]+1,seg[v]));
	return tmp;
}

int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)	fa[i] = i;
	for(int i=1,x,y,z;i<=m;i++){
		x=read();y=read();z=read();
		if(x==y) continue;
		build(x,y,z);
		pq.push(bian[ee]);
	}
	kruscal();
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			dfs1(i,0);
			val[i] = 100005;
			vis[i] = true;
		}
	memset(vis,0,sizeof(vis));
	seg[0] = 0;
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			seg[i]=++seg[0];
			rev[seg[0]]=top[i]=i;		
			dfs2(i);
		}
//	for(int i=1;i<=n;i++)
//		cout<<i<<" "<<father[i]<<" "<<son[i]<<" "<<depth[i]<<" "<<size[i]<<" "<<top[i]<<" "<<seg[i]<<endl;
//	cout<<endl; 
	create(1,1,n);
//	for(int i=1;i<=n;i++)
//		cout<<val[i]<<" ";
//	tiaoshi(1,1,n);	
//	cout<<endl;
	q=read();
	for(int i=1,x,y;i<=q;i++){
		x=read();y=read();
		if(find(fa[x])!=find(fa[y])) printf("-1\n");
		else printf("%d\n",query(x,y));
	}
	return 0;
}
           

從昨天晚上改到今天下午 從MLE+WA到MLE+RE+WA到95到今天下午改成剖森林最後AC！

遇到的問題：

• 并查集沒學到位 k1 k2要寫好（小心寫錯）

//relative
#include<iostream>
using namespace std;
int father[20005];

int find(int x){	
	if (father[x]!=x) return father[x]=find(father[x]);
	else return x;
}

int main(){
	int n,m,q;
	cin>>n>>m;
	for (int i=1;i<=n;i++) father[i] = i;
	for (int i=0,x,y,k1,k2;i<m;i++){
		cin>>x>>y;
		k1 = find(x);
		k2 = find(y);
		if (k1!=k2) father[k2] = k1;
	}
	cin>>q;
	for (int i=0,x,y;i<q;i++){
		cin>>x>>y;
		if (find(x)==find(y)) cout<<"Yes\n";
		else cout<<"No\n";
		}
	return 0;
}
           

• 樹剖create總是在tree[rt] = w[?] 的問号處寫錯！！應該是rev[L]
• kruscal之前不用建雙向邊，kruscal選出來的邊再雙向
• 要剖森林啊啊啊啊啊啊啊啊啊啊啊啊
• 用Bian這個名字容易遭到别人的吐槽

2019.11.13. — 2019.11.14.