杭电1269迷宫城堡（二维并查集过） - CSDN博客
杭电1269迷宫城堡（二维并查集过）
Problem Description
Sample Input
Sample Output
炸一看知道是并查集~再一看还知道是并查集，但是要咋写呢~
这里直接上实例：
一般的并查集的题目可以理解为单源连通图，比如并查集数组pre[]中存数据如下：3 3 3，我们知道 点1的祖先是3号，1-&...-&3，同理，2号的祖先也是3号2-&.....-&3无论中间是否有繁杂的路径，我们知道1 2 的祖先是3，但是3的祖先一定不可能是1 2 。
本题题意是说，所有的房间都连通，如果说1 2 3 4 5 6....n-1的找到的祖先都是n并且反过头说，n也能找到1 2 3 4 5 6...n-1我们就构成了这个条件：所有房间都连通.
因为我们知道一维的并查集数组可以完成单向完成查找，如果反过去也能找的话就能说所有的房间都连通了.
这里先贴上一维并查集数组的merge操作：
void merge(int a,int b)
A=find(a);
B=find(b);
f[B]=A;//f[A]=B;
}这里我们只能完成B-&A或者是A-&B 的操作，如果我们能同时操作就完美的实现了刚才的理论：用两个数组来实现.
void merge(int a,int b)
int fa=find(a,0),fb=find(b,0);
if(fa!=fb)
pre[0][a]=b;//这里应用了二维数组.表示有两个并查集数组.
int fa=find(a,1),fb=find(b,1);
if(fa!=fb)
pre[1][b]=a;
这个时候我们把所有房间都理解成为一个环：
正向查找到n的同时逆向也能查找到n就满足了环，同时满足所有房间都连通。然后贴上完整AC代码：
#include&stdio.h&
#include&string.h&
int pre[2][100010];
int find(int a,int i)
while(r!=pre[i][r])
r=pre[i][r];
void merge(int a,int b)
int fa=find(a,0),fb=find(b,0);
if(fa!=fb)
pre[0][a]=b;
int fa=find(a,1),fb=find(b,1);
if(fa!=fb)
pre[1][b]=a;
int main()
while(scanf(&%d%d&,&n,&m)!=EOF,n||m)
if(n==0||m==0)
for(int i=0;i&=n;i++)
pre[0][i]=pre[1][i]=i;
while(m--)
scanf(&%d%d&,&a,&b);
merge(a,b);
/*for(int i=1;i&=3;i++)
printf(&%d &,pre[0][i]);
for(int i=1;i&=3;i++)
printf(&%d &,pre[1][i]);
for(int i=1;i&=n;i++)
// printf(&%d %d\n&,find(i,0),find(i,1));
if(find(i,0)!=n||find(i,1)!=n)
printf(&Yes\n&);
printf(&No\n&);
本文已收录于以下专栏：
相关文章推荐
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Subm...
上一篇博文我们讲了如何看到实验结果，这篇博文我们着重分析源代码。
书中作者为了说明原理，约定了一种比较简单地用户程序头部格式，示意图如下（我参考原书图8-15绘制的，左边的数字表示偏移地址）：
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Submi...
解题思想：通过利用设定1为根节点，然后建立以1为根的树，查找时，如果所有节点都是以1为根，则说明单向互通；然后再逆序采用相同的操作，如果逆序得到的所有节点也是以1为根，则说明逆向互通，此时说明图为强连...
迷宫城堡Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Submis...
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Sub...
Problem Description
上次Gardon的迷宫城堡小希玩了很久（见Problem B），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该...
小希的迷宫
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Su...
今天，刚学习了并查集对于并查集，也有了一定的理解了。
杭电1272这一题，主要是给你几对数，表示这两个数（可以理解为村落）直接有路，而从每一个村落到另外一个村落只能有一条路，也就是不能存在环。而并查...
思路：这题运用到tarjan算法 刚看这个算法一脸蒙b，然后通过阅读别人的博客算是掌握的差不多了。这个算法中用到两个数组第一个dfn[],low[],第一个数组是用来记录深搜的顺序的，第二个数组是用来...
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)【BZOJ】3631 [JLOI2014]松鼠的新家 LCA+树上差分 - CSDN博客
【BZOJ】3631 [JLOI2014]松鼠的新家 LCA+树上差分
再水一篇blog，可能也是我专门去学树上差分的最后一题吧。
一开始拿到题目，并没有想到树上差分的做法，看了题解之后：原来差分还可以这么用的啊，又学到了一种黑科技。
对于相邻的两个房间，直接和“【BZOJ】4390 [Usaco2015 dec]Max Flow”这题一样差分就好了。（真的就好了吗？）
重新考虑一下，发现从第i个房间走到第i+1个房间和从第i+1个房间走到第i+2个房间是同一条路径，但是第i+1个房间被计算了两次。
那么在此考虑，是不是除了起点外的房间都多计算了一次呢？的确如此。
于是直接把除了起点外的所有点都打上-1的标记再O(n)遍历一遍就行了。
附上AC代码：
#include &cstdio&
#include &cctype&
#include &algorithm&
using namespace std;
const int N=3e5+10;
struct side{
int n,x,y,num,h[N],t,sum[N],a[N];
int d[N],sz[N],hs[N],f[N],top[N];
inline char nc(){
static char ch[100010],*p1=ch,*p2=
return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++;
inline void read(int &a){
static char c=nc();int f=1;
for (;!isdigit(c);c=nc()) if (c=='-') f=-1;
for (a=0;isdigit(c);a=a*10+c-'0',c=nc());
return (void)(a*=f);
inline void add(int x,int y){
s[++num]=(side){y,h[x]},h[x]=
s[++num]=(side){x,h[y]},h[y]=
inline void so1(int x,int fa){
d[x]=d[f[x]=fa]+1,sz[x]=1;
for (int i=h[x]; i=s[i].nt)
if (s[i].to!=fa){
so1(s[i].to,x),sz[x]+=sz[s[i].to];
if (sz[s[i].to]&sz[hs[x]]) hs[x]=s[i].
inline void so2(int x,int fa){
if (hs[x]) so2(hs[x],fa);
for (int i=h[x]; i=s[i].nt)
if (s[i].to!=f[x]&&s[i].to!=hs[x]) so2(s[i].to,s[i].to);
inline int query(int x,int y){
for (int fx=top[x],fy=top[y]; fx!= x=f[fx],fx=top[x])
if (d[fx]&d[fy]) swap(fx,fy),swap(x,y);
return d[x]&d[y]?x:y;
inline void so(int x){
for (int i=h[x]; i=s[i].nt)
if (s[i].to!=f[x]) so(s[i].to),sum[x]+=sum[s[i].to];
int main(void){
for (int i=1; i&=n; ++i) read(a[i]);
for (int i=1; i&n; ++i) read(x),read(y),add(x,y);
so1(1,0),so2(1,1);
for (int i=1; i&n; ++i){
t=query(a[i],a[i+1]);
++sum[a[i]],++sum[a[i+1]],--sum[t],--sum[f[t]];
for (int i=2; i&=n; ++i) --sum[a[i]];
for (int i=1; i&=n; ++i) printf("%d ",sum[i]);
本文已收录于以下专栏：
相关文章推荐
3631: [JLOI2014]松鼠的新家Time Limit: 10 Sec
Memory Limit: 128 MB
Submit: 1643
Solved: 776
[Submit][S...
题很水，人比某Qwsin更蠢。
dfs2里面递归写成了dfs…orz…跪了..
我还以为前面挂了结果最后算sum的时候..#include
省选的day1第一题，当时不会树链剖分，写
题目大意：给定一棵无根树和一个序列，在这个序列上依次遍历，求每个点的访问次数(最后一个点的访问次数要-1)
树链剖分的裸题……考场上我还是一个弱渣，啥也不会，暴力得了50分，剩下两道题爆零了。。。而...
直接进行树链剖分
每一轮，路径上的点加1
最后输出***时，除起点外的结点权值要减1
只用到区间增减，单点查询和值，因此并不需要线段树来维护
另一种思路：类似前缀和的思想
从起点x到...
一眼看去，就是shu'zhuang'hsu'z
Description松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请...
深院青墙，梧桐秋雨，寂寞锁寒。
题目大意：从编号1到n遍历图（中间经过点不算遍历过），求每个点经过了几次
树剖，每次i到i+1都相当于一次链上修改，最后单点查询就行。
题意: 给你一棵无向的树,然后给你这棵树的节点访问次序,起点任意,求每个节点的访问次数.
方法: 离线tarjan lca.
解析: (果然自己还是弱啊,结尾标记都不会传) , 膜拜神?orz
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)