【BZOJ 4883】[Lydsy2017年5月月赛] 棋盘上的守卫

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4883
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

把行和列看成点,格子看成边
那么一个$n$个点的连通块需要$n$条边
于是用$Kruskal$做一个基环树森林就可以了
时间复杂度:$O(nm \log nm)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000;

struct Edge{
	int u, v, c;
	bool operator < (const Edge &ee) const {
		return c < ee.c;
	}
}e[N];
int n, m, tot, cir[N], fa[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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;
}

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

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			e[++tot].c = read();
			e[tot].u = i;
			e[tot].v = n + j;
		}
	}
	sort(e + 1, e + 1 + tot);
	for (int i = 1; i <= n + m; i++) {
		fa[i] = i;
	}
	LL ans = 0;
	for (int i = 1; i <= tot; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (cir[fu] && cir[fv]) {
			continue;
		} else if (fu != fv) {
			fa[fv] = fu;
			cir[fu] |= cir[fv];
		} else if (!cir[fu]) {
			cir[fu] = 1;
		}
		ans += e[i].c;
	}
	printf("%lld\n", ans);
	return 0;
}

【BZOJ 2521】[SHOI2010] 最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2521
神犇题解:http://krydom.com/bzoj2521/

解题报告

这题有一个非常显然的贪心:做Kruskal的时候,如果会使那条边的两个端点连在一起就暴力加权值
但这样显然也是错误的,因为我们可能是在之前的步骤就废掉一些边
于是怎么解决这个问题呢?
我们相当于不能在某两个端点之间有通路,那么这和网络流的增广路相同
于是我们把边的容量设为暴力改的时候需要的花费,然后跑一遍最小割就可以了

【BZOJ 3551】[ONTAK2010] Peaks加强版

相关链接

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

解题报告

这题强制在线,所以不能直接上启发式合并
或者强行可持久化也可以?
不过我们有更加优美的东西:Kruskal重构树

就是按照边权排序,然后做Kruskal
如果需要加边,那么我们新建一个结点,权值设为这条边的权值
然后把原来的两个点连到这个点下面当儿子
于是任意两点之间的最大边权就是他们的LCA的权值了

对于原题来讲,我们可以先倍增到最浅的可以到达的祖先
那么这个祖先的子树就是可以到达的所有点了
考虑DFS序,问题变为区间k大,这是主席树的经典应用
于是这题就做完啦!

今天上午考试考了一道类似的题目,然而忘了这个做法
是用的线段树合并+标记永久化,虽然能A但显然不如这个优雅

【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解:http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想,这题似乎除了有加油站的点之外,其他点似乎完全可以不用考虑?
再仔细想一想的话,我们似乎只要求出任意两个有加油站的点的最短路,然后再做一个MST就可以了!

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件,求出一些最短路径的集合 $\{ e \}$ ,使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质:

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上,一定是前一部分$blg(x)=a$,后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢?考虑反证法:如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油,回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来,做一个最小生成树,然后查询的时候,在树上倍增一下就可以啦!

【BZOJ 2001】[HNOI2010] City 城市建设

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2001
神犇题解Ⅰ:http://www.cnblogs.com/BLADEVIL/p/3512644.html
神犇题解Ⅱ:http://blog.miskcoo.com/2015/04/bzoj-2001

解题报告

如果没有边权,只需要维护连通性
那么搞一个可以撤销的并查集就可以啦!

现在考虑带边权的情况,我们仍然对时间进行分治
在每一层,我们进行两个操作:

1. Contraction 缩小点的规模

将所有当前分治区间内会被修改的边的边权置为 $-INF$
然后做一遍MST,将此时通过非 $-INF$ 连接的点用并查集缩起来
因为$-INF$边只会有区间长度个,所以每一次分治后,点的规模不会超过分治区间的长度

2. Reduction 缩小边的规模

将会被修改的边的边权置为 $INF$,然后再做一遍MST
将此时不在MST中的边删去,因为保留的边数不会超过点数,所以边的规模也不会超过分治区间的长度

所以时间复杂度写出来长这样: $T(n) = 2T(\frac{n}{2}) + n\log n$
用主定理化简之后,时间复杂度就是: $O(n{\log ^2}n)$

【AtCoder】[CODE FESTIVAL 2016 Final G] Zigzag MST

相关链接

题目传送门:http://cf16-final.contest.atcoder.jp/tasks/codefestival_2016_final_g
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/01/atcoder_codefestival_2016_final_g.pdf

解题报告

这题好神啊!现在感觉每道题都好神啊!

先来看任意一个连边操作:

考虑正常的最小生成树算法,如果用到了价值为 $ c+1$ 的边,那么价值为 $ c$ 的边一定已经考虑过了
于是我们就可以把图等价地变换为下面这个样子:

这样的话,我们可以把价值为 $ c$ 地那一类边拿出来单独考虑
余下的边搞一个堆,连一圈
这样的话,我们的图就改造成了这个样子:

此时我们的边就只剩 $ N+Q$ 条了,直接跑最小生成树算法就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 400000+9;

struct Edge{int u,v,w;}e[N];
struct Operation{int p,c;}op[N];
priority_queue<Operation> que;
int n,m,tot,vis[N],fa[N]; LL vout;

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

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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;
}

int main() {
	n = read(); m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read();
		e[++tot] = (Edge){a, b, c};
		que.push((Operation){a, c+1});
		que.push((Operation){b, c+2});
	}
	while (!que.empty()) {
		Operation w = que.top(); que.pop();
		if (!vis[w.p]) {
			vis[w.p] = 1;
			e[++tot] = (Edge){w.p, (w.p+1)%n, w.c};
			que.push((Operation){(w.p+1)%n, w.c+2});
		}
	}
	sort(e+1, e+1+tot);
	for (int i=0;i<=n;i++) fa[i] = i;
	for (int i=1;i<=tot;i++) {
		if (find(e[i].u) != find(e[i].v)) {
			fa[fa[e[i].u]] = fa[e[i].v];
			vout += e[i].w;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【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 1016】[JSOI2008] 最小生成树计数

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1016
优秀题解:https://blog.sengxian.com/solutions/bzoj-1016

题解

考虑最小生成树,如果使用价值相同的非树边边替换树边,得到的效果一定一样
因为不一样的话,用于替换的边就会成为最小生成树的树边
换一句话来说,权值相同的边处理完之后,图的连通性一定一样

于是暴力枚举同一权值的边的组合情况
使用并查集判断一下即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int M = 1000+9;
const int MOD = 31011;

struct Edge{int u,v,w;}e[M];
vector<Edge> que[M];
int n,m,fa[N],fa_tmp[N],_hash[M],cnt[M],tot,vout=1,vis[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 (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

void DFS(int w, int sz, int cur, int id, int &tmp) {
	if (cur > cnt[id]) {
		return ;
	} else if (w == sz + 1) {
		if (cur == cnt[id]) {
			memcpy(fa_tmp, fa, sizeof(fa));
			int i; for (i=1;i<=sz;i++) if (vis[i]) {
				if (find(que[id][i-1].u) == find(que[id][i-1].v)) break;
				fa[find(que[id][i-1].u)] = find(que[id][i-1].v);
			}	
			tmp += (i == sz + 1);
			memcpy(fa, fa_tmp, sizeof(fa));
		}
	} else {
		DFS(w+1, sz, cur, id, tmp);
		vis[w] = 1;
		DFS(w+1, sz, cur+1, id, tmp);
		vis[w] = 0;
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		e[i].u = u = read(); 
		e[i].v = v = read();
		_hash[i] = e[i].w = read();
	}
	sort(_hash+1, _hash+1+m);
	tot = unique(_hash+1, _hash+1+m) - _hash - 1;
	for (int i=1,tmp;i<=m;i++) {
		tmp = lower_bound(_hash+1, _hash+1+tot, e[i].w) - _hash;
		que[tmp].push_back(e[i]);
	}
	for (int i=1;i<=n;i++)
		fa[i] = i;
	for (int i=1;i<=tot;i++) {
		for (int j=que[i].size()-1;~j;j--) {
			if (find(que[i][j].u) != find(que[i][j].v)) {
				fa[find(que[i][j].u)] = find(que[i][j].v);
				cnt[i]++;
			}
		}
	} 
	for (int i=2;i<=n;i++) {
		if (find(i) != find(1)) {
			puts("0");
			exit(0);
		}
	}
	
	for (int i=1;i<=n;i++) 
		fa[i] = i;
	for (int i=1,tmp=0;i<=tot;i++,tmp=0) if (cnt[i]) {
		DFS(1,que[i].size(),0,i,tmp);
		for (int j=que[i].size()-1;~j;j--) 
			fa[find(que[i][j].u)] = find(que[i][j].v);
		(vout *= tmp) %= MOD;
	}
	printf("%d\n",vout);
	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;
}

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