【BZOJ 2654】tree

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2654
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/47980565

题解

感觉这个题很好玩的样子!
考虑给每一个白边加上一个固定的权值
那么使用白边的数量可以用这个权值来调整
唯一需要注意的就是,这种变化可能不是线性的
也就是说可能会有断层的情况,需要特殊处理一下

值得注意的是,这种方法具有较高的可移植性:
在某一套小火车的模拟题中,一道很恶心的DP也可以用此方法来解决

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
 
struct Edge{int u,v,val,col;}e[N]; 
int n,m,STA,fa[N];
 
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline int find(int w) {
    int f = fa[w], tmp;
    while (f != fa[f]) f = fa[f];
    while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
    return f;
} 
 
bool cmp_mx(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col > B.col);}
bool cmp_mn(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col < B.col);}
 
inline bool judge(int delta) {
    int cnt = 0;
    sort(e+1, e+1+m, cmp_mx);
    for (int i=1;i<=n;i++) fa[i] = i;
    for (int i=1;i<=m;i++) {
        if (find(e[i].u) != find(e[i].v)) {
            fa[find(e[i].u)] = find(e[i].v);
            cnt += e[i].col;
        }
    }
    if (cnt < STA) return 1;
     
    int cost = 0; cnt = 0;
    sort(e+1, e+1+m, cmp_mn);
    for (int i=1;i<=n;i++) fa[i] = i;
    for (int i=1;i<=m;i++) {
        if (find(e[i].u) != find(e[i].v)) {
            fa[fa[e[i].u]] = fa[e[i].v];
            cnt += e[i].col;
            cost += e[i].val; 
        }
    }
    if (cnt > STA) return 0;
    else {
        printf("%d\n",cost-STA*delta);
        exit(0);
    }
}
 
int main(){
    n = read(); m = read(); STA = read();
    for (int i=1;i<=m;i++) {
        e[i].u = read() + 1; e[i].v = read() + 1;
        e[i].val = read(); e[i].col = read() ^ 1;
    } 
     
    int l=-100,r=100,mid;
    while (l <= r) {
        mid = l + r >> 1;
        for (int i=1;i<=m;i++) if (e[i].col) e[i].val += mid;
        if (judge(mid)) r = mid - 1;
        else l = mid + 1;
        for (int i=1;i<=m;i++) if (e[i].col) e[i].val -= mid;
    } 
    return 0;
}

【BZOJ 3943】[Usaco2015 Feb] SuperBull

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3943
离线版题目:http://paste.ubuntu.com/23080229/

XOR意义下的位运算生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int N = 2000+9;
const int M = N*32;
const int SGZ = 2;

int n,arr[N],fa[N],to[N],val[N];
LL vout;

namespace Trie{
	int MX[M],MN[M],ch[M][SGZ],cnt,root,NUM,COL,ans_tmp;
	
	inline void init(){
		memset(MX,-1,sizeof(MX));
		memset(MN,-1,sizeof(MN));
		memset(ch,0,sizeof(ch));
		cnt = root = 0;
	}
	
	void Insert(int &w, int t){
		if (!w) w = ++cnt; 
		if (!~MX[w] || MX[w] < COL) MX[w] = COL;
		if (!~MN[w] || MN[w] > COL) MN[w] = COL;
		if (t) Insert(ch[w][(NUM&t)>0],t>>1);  
	}
	
	inline void insert(int num, int col){
		if (!root) root = ++cnt;
		NUM = num, COL = col;
		Insert(ch[root][(num&(1<<30))>0],1<<29);
	}
	
	void Query(int w, int t){
		if (t) {
			int to = ch[w][((NUM&t)>0)^1];
			if (to && (MX[to] != COL || MN[to] != COL)) ans_tmp |= t, Query(to,t>>1);
			else Query(ch[w][(NUM&t)>0],t>>1);
 		} else {
			if (COL != MN[w]) COL = MN[w];
			else COL = MX[w]; 	
		}
	} 
	
	inline pair<int,int> query(int num, int col){
		ans_tmp = 0; NUM = num; COL = col;
		Query(root,1<<30);
		return make_pair(ans_tmp,COL);
	}
};

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret; 
}

int main(){
	n = read(); int cnt = n-1;
	for (int i=1;i<=n;i++) arr[i] = read(), fa[i] = i;
	while (cnt) {
		Trie::init(); 
		memset(val,0,sizeof(val));
		for (int i=1;i<=n;i++) Trie::insert(arr[i],find(i));
		for (int i=1;i<=n;i++) {
			pair<int,int> tmp = Trie::query(arr[i],fa[i]);
			if (tmp.first > val[fa[i]]) val[fa[i]] = tmp.first, to[fa[i]] = tmp.second;
		}
		for (int i=1;i<=n;i++) if (to[i] && find(to[i]) != find(i)) 
			vout += val[i], fa[find(i)] = find(to[i]), cnt--;
	}
	printf("%lld\n",vout);
	return 0;
}

不过貌似这个题直接暴力就行了?

【HDU 5627】Clarke and MST

题目传送门:http://acm.split.hdu.edu.cn/showproblem.php?pid=5627
吐槽:HDU你好好的,为什么要加一个split?你TM还会分身了?

本来以为是位运算生成树,结果不是QAQ
管他的,看都看到了就来练练手
结果居然被这种题目给卡常了,cin在HDU上真是慢得一逼╮(╯▽╰)╭

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 300000+9;

struct Edge{int u,v,val;}e[N];
int n,m,fa[N];

inline int find(int w){
	int f=fa[w],tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

inline bool test(int x) {
	x = 1<<x-1; int tag = n-1;
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int i=1;i<=m;i++) if (e[i].val & x) 
		if (find(e[i].u) == find(e[i].v)) continue;
		else fa[find(e[i].u)] = find(e[i].v), tag--;
	if (!tag) { 
		int tmp=0;
		for (int i=1;i<=m;i++) if (e[i].val & x) e[++tmp] = e[i];
		m = tmp; return true;
	} else return false;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
	return ret;
}

int main(){
	int T; cin>>T; while (T--) {
		cin>>n>>m; int tag = n-1, vout = 0;
		for (int i=1;i<=n;i++) fa[i] = i;
		for (int i=1;i<=m;i++) {
			e[i].u = read(); e[i].v = read(); e[i].val = read();
			if (find(e[i].u) == find(e[i].v)) continue;
			else fa[find(e[i].u)] = fa[find(e[i].v)], tag--;
		}
		if (tag) printf("0\n");
		else {
			for (int i=31;i;i--) if (test(i)) vout |= 1<<i-1;
			printf("%d\n",vout);
		}
	}
	return 0;
}

【UOJ 176】新年的繁荣

题目传送门:http://uoj.ac/problem/176

位运算生成树系列之&最大
详细情况,见之后的算法笔记吧

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int N = 1<<19;

int n,m,num[N],fa[N];
LL vout;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

int main(){
	n = read(); m = read();
	for (int i=1,v;i<=n;i++) 
		if (num[v=read()]) vout += v;
		else num[v] = v;
	for (int q=(1<<m)-1;q;q--) { fa[q] = q;
		for (int i=1;i<=m && !num[q];i++) num[q] = num[q|1<<i-1];
		for (int i=1,f1,f2,u=num[q],v;i<=m;i++) 
			if ((v=num[q|1<<i-1]) && find(u) != find(v)) vout += q, fa[find(u)] = find(v);
	}
	printf("%lld\n",vout);
	return 0;
}

来补一个Boruvka + trie的版本:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define R(x) ((x)>0)
using namespace std;

const int N = 100000+9;
const int M = N*32*4;

int n,arr[N],v[N],sur[N],fa[N],m;
LL vout = 0;

namespace Trie{
	int root,ch[M][2],MX[M],MN[M],cnt,NUM,COL,ans_tmp;
	
	inline void init(){
		memset(ch,0,sizeof(ch));
		memset(MX,0,sizeof(MX));
		memset(MN,0,sizeof(MN));
		cnt = root = 1;
	}
	
	void Insert(int &w, int t){
		if (!w) w = ++cnt;
		if (!MX[w] || MX[w] < COL) MX[w] = COL;
		if (!MN[w] || MN[w] > COL) MN[w] = COL;
		if (t) Insert(ch[w][R(NUM&t)],t>>1);
	}
	
	inline void insert(int num, int col){
		NUM = num; COL = col;
		Insert(ch[root][R(num&(1<<m))],1<<m-1);
	}
	
	void Merge(int &w, int p){
		if (!w) w = ++cnt;
		if (!MX[w] || MX[w] < MX[p]) MX[w] = MX[p];
		if (!MN[w] || MN[w] > MN[p]) MN[w] = MN[p];
		
		if (ch[p][0]) Merge(ch[w][0], ch[p][0]);
		if (ch[p][1]) Merge(ch[w][1], ch[p][1]);
	}
	
	void merge(int w){
		if (ch[w][1]) Merge(ch[w][0],ch[w][1]), merge(ch[w][1]);
		if (ch[w][0]) merge(ch[w][0]); 
	}
	
	void Query(int w, int t){
		if (t) {
			if (R(NUM&t) && (MN[ch[w][1]] != COL || MX[ch[w][1]] != COL)) ans_tmp|=t, Query(ch[w][1], t>>1); 
			else Query(ch[w][0],t>>1);
		} else {
			if (MN[w] != COL) COL = MN[w];
			else COL = MX[w];
		}
	}
	
	inline pair<int,int> query(int num, int col){
		ans_tmp = 0; NUM = num, COL = col;
		Query(root,1<<m);
		return make_pair(ans_tmp,COL);
	}
};

inline int find(int w){
	int f=fa[w], tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

int main(){
	n = read(); m = read(); int cnt = n-1;
	for (int i=1;i<=n;i++) fa[i] = i, arr[i] = read();
	while (cnt) {
		Trie::init(); memset(v,-1,sizeof(v));
		for (int i=1;i<=n;i++) Trie::insert(arr[i],find(i));
		Trie::merge(Trie::root);
		for (int i=1;i<=n;i++) {
			pair<int,int> tmp = Trie::query(arr[i],fa[i]);
			if (tmp.first > v[fa[i]]) v[fa[i]] = tmp.first, sur[fa[i]] = tmp.second;
		}
		for (int i=1;i<=n;i++) if (~v[i] && find(i) != find(sur[i])) 
			vout += v[i], fa[find(i)] = find(sur[i]), cnt--;
	}
	printf("%lld\n",vout);
	return 0;
}

【POJ 3522】Slim Span

题目传送门:http://poj.org/problem?id=3522

今天在水位运算生成树,无聊来水一水
很暴力,枚举最大边,然后搞一搞,并查集判树

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100+9;
const int M = 10000+9;
const int INF = 1000000000;

struct Edge{int u,v,w;}e[M];
int n,m,vout,fa[N];

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline int Get_Ans(int lim){
	for (int i=1;i<=n;i++) fa[i] = i;
	fa[e[lim].u] = fa[e[lim].v];
	for (int i=lim-1,t=n-2,f1,f2;i;i--) {
		f1 = find(e[i].u); f2 = find(e[i].v);
		if (f1 != f2) fa[f2] = f1, t--;
		if (!t) return e[i].w;
	}
	return -INF;
}

int main(){
	while (scanf("%d%d",&n,&m) && (n||m)) {
		for (int i=1;i<=m;i++) e[i].u = read(), e[i].v = read(), e[i].w = read();
		sort(e+1,e+1+m); vout = INF;
		for (int lim=m;lim>=n-1;lim--) 
			vout = min(vout, e[lim].w - Get_Ans(lim));
		if (n <= 2) printf("0\n");
		else printf("%d\n",vout>=INF?-1:vout);	
	}
	return 0;
}

【BZOJ 2429】[HAOI2006] 聪明的猴子

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2429

MST的板题,MST搞出来,再拿每一个猴子比一比就好
好吧,其实我是来练Boruvka的……

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}

【模板库】Borůvka’s algorithm

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2429
参考代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}

算法简介:https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
算法正确性证明:http://oi.cyo.ng/wp-content/uploads/2016/08/02345678641.png
国外带注释模板:http://www.geeksforgeeks.org/greedy-algorithms-set-9-boruvkas-algorithm/