题解 - Vijos

0

芒果木瓜榴莲 LV 9 @ 2009-09-12 21:51:10

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

突然发现了并查集的惊天秘密……

const filename='p1034';

var

a:array[1..5000]of longint;

i,j,n,m,p,x,y,z1,z2:longint;

function find(i:longint):longint;

begin

if a[i]=0 then exit(i); {

0

mintalfance LV 10 @ 2009-09-11 11:50:56

program p1034;

var a:array[1..5000] of longint;

i,j,k,l,m,n,p,q,r:longint;

begin

for i:=1 to 5000 do a[i]:=i;

readln(n,m,r);

for i:=1 to m do

begin readln(p,q);

for j:=1 to n do

if (a[j]=a[q]) and (jq) then a[j]:=a[p];

a[q]:=a[p];

end;

for i:=1 to r do begin

readln(p,q);if a[p]=a[q] then writeln('Yes') else writeln('No');

end;

end.

第一次写并查集。。。练手

0

超子 LV 9 @ 2009-09-10 19:28:30

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

并查集第一题——纪念………

0

石明鑫 LV 8 @ 2009-09-09 19:38:03

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

今天学了并查集,第一题练手!

这道题太可爱了!

0

lyyqy0910 LV 7 @ 2009-09-06 17:06:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include

#define MAX 20001

int n,m,p;

int parent[MAX],rank[MAX];

void make_set(int i)

{

parent[i]=-1;

rank[i]=0;

}

int find(i)

{

if(parent[i]!=-1)

parent[i]=find(parent[i]);

if(parent[i]==-1)

return i;

else return parent[i];

}

void union_set(int i,int j)

{

int root1,root2;

root1=find(i);

root2=find(j);

if(root1!=root2)

{

if(rank[root1]>rank[root2])

parent[root2]=root1;

else{

parent[root1]=root2;

if(rank[root1]==rank[root2])

++rank[root2];

}

}

}

int main()

{

int i,a,b,c,d;

scanf("%d %d %d",&n,&m,&p);

for(i=1;i

0

xudyh LV 10 @ 2009-09-05 15:09:29

真是RP问题吗？

0

code-geass LV 9 @ 2009-08-25 08:52:18

纯冰茶..........

0

testla LV 7 @ 2009-08-15 15:12:46

var

c,d,n,m,p,i,j:longint;

a:array[1..5000]of longint;

begin

for i:=1 to 5000 do a[i]:=i;

readln(n,m,p);

for i:=1 to m do

begin

readln(c,d);

for j:=1 to n do if (a[j]=a[d])and(jd) then a[j]:=a[c];

a[d]:=a[c];

end;

for i:=1 to p do

begin

readln(c,d);

if a[c]=a[d] then writeln('Yes') else writeln('No');

end;

end.

0

xhm2992 LV 7 @ 2009-08-15 00:54:19

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

哈哈，碰到的第一个并查集，开门红啊！（不过看来这题确实简单..）

0

zhanghanyuan LV 10 @ 2009-08-10 15:03:21

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

MS

0

飘の★ LV 10 @ 2009-08-06 23:56:29

标准的并查集。。。轻易的秒杀。。

0

青岚 LV 4 @ 2009-08-05 14:34:06

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒掉！

program p1034;

var

pa,a,b,c,d:array[1..5001] of longint;

a1,b1,p,i,j,k,l,e,w,q,s,z,xx,yy,x,y,max,min,m,n:longint;

function find(x:longint):longint;

var

i,j,k:longint;

begin

k:=x;

while xpa[x] do

x:=pa[x];

pa[k]:=x;

find:=x;

end;

procedure union(x,y:longint);

var

i,j,k:longint;

begin

if x

0

BeWinDe LV 7 @ 2009-08-05 14:20:12

var a,g:array[1..5000]of longint;

i,j,k,l,n,m,p,x,y:longint;

begin

read(n,m,p);

for i:=1 to n do a[i]:=i;

for i:=1 to m do

begin

read(x,y);k:=a[y];

for j:=1 to n do if a[j]=k then a[j]:=a[x];

end;

for i:=1 to p do

begin

read(x,y);

if a[x]=a[y] then g[i]:=1

else g[i]:=0;

end;

for i:=1 to p do if g[i]=1 then writeln('Yes')

else writeln('No');

end.

多么简洁啊

0

27JZY LV 8 @ 2009-08-03 20:15:50

#include

using namespace std;

int n,m,p,a[5001];

void union1(int R1, int R2)

{

if(a[R2]n>>m>>p;

for(i=1;ix1>>x2;

f1=find1(x1);

f2=find1(x2);

if(f1!=f2)union1(f1,f2);

}

for(i=1;i>y1>>y2;

f1=find1(y1);

f2=find1(y2);

if (f1==f2)

cout

0

jiamomo LV 7 @ 2009-07-29 15:30:47

我们把一个连通块看作一个集合，问题就转化为判断两个元素是否属于同一个集合。假设一开始每个元素各自属于自己的一个集合，每次往图中加一条边a－b，就相当于合并了两个元素所在集合A和B，因为集合A中的元素用过边a－b可以到达集合B中的任意元素，反之亦然。当然如果a和b本来就已经属于同一个集合了，那么a-b这条边就可以不用加了。（1）具体操作：① 由此用某个元素所在树的根结点表示该元素所在的集合；② 判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样即可；③ 也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可。（2）元素的合并图示：（3）判断元素是否属于同一集合：用father[i]表示元素i的父亲结点，如刚才那个图所示：faher[1]:=1；faher[2]:=1；faher[3]:=1；faher[4]:=5；faher[5]:=3至此，我们用上述的算法已经解决了空间的问题，我们不再需要一个n2的空间来记录整张图的构造，只需要用一个记录数组记录每个结点属于的集合就可以了。但是仔细思考不难发现，每次询问两个元素是否属于同一个集合我们最多还是需要O(n)的判断！3. 算法3，并查集的路径压缩。算法2的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见判断两个元素是否属于同一集合需要O(n)的时间，于是路径压缩产生了作用。路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向3，而是直接指向根节点1，由此我们得到了一个复杂度只是O(1)的算法。

0

lishunzhi LV 9 @ 2009-07-28 10:49:50

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var a:array[0..10000]of longint; m,i,t,fx,fy,n,x,y:longint;

function find(x:longint):longint;

begin

if x=a[x] then find:=a[x]

else find:=find(a[x]);

end;

begin

readln(n,m,t);

for i:=1 to n do

begin

a[i]:=i;

// dep[i]:=0;

end;

for i:=1 to m do

begin

readln(x,y);

fx:=find(x);

fy:=find(y);

a[fx]:=fy;

end;

for i:=1 to t do

begin

readln(x,y);

fx:=find(x);

fy:=find(y);

if fx=fy then writeln('Yes') else write('No');

end;

end.

无须优化,直接秒杀

0

363059129 LV 10 @ 2009-07-25 10:49:55

var father,rank:array[1..10000]of longint;

x,y,t,tt,n,m,p,i:longint;

function find(x:longint):longint;

begin

if father[x]=x then exit(x);

father[x]:=find(father[x]);

exit(father[x]);

end;

begin

read(n,m,p);

for i:=1 to n do begin father[i]:=i;rank[i]:=1;end;

for i:=1 to m do

begin

read(x,y);

t:=find(x);

tt:=find(y);

if rank[t]>rank[tt] then father[tt]:=t

else if rank[t]

0

水玉 LV 7 @ 2009-07-15 15:57:10

总以为错了，原来少打了 getfather(...)...

var

n,m,p,i,x,y:integer;

father:array[0..6000] of integer;

function getfather(i:integer):integer;

begin

if father[i]=i then exit(i)

else begin

father[i]:=getfather(father[i]);

exit(father[i]);

end;

end;

begin

readln(n,m,p);

for i:=1 to n do father[i]:=i;

for i:=1 to m do

begin

readln(x,y);

father[getfather(y)]:=getfather(x);

end;

for i:=1 to p do

begin

readln(x,y);

if getfather(father[x])=getfather(father[y]) then writeln('Yes')

else writeln('No');

end;

end.

0

1s LV 10 @ 2009-07-11 23:20:31

沙茶题留名……

0

Program饭 LV 8 @ 2009-07-09 20:23:59

orz 终于会并查集了……

下个月再做一遍。

#include

#include

int n,m,p;

int b[1000],f[6001]={0};

void judge(int x,int y)

{

int fx,fy;

fx=getfather(x);

fy=getfather(y);

if(fx==fy) return;

else

f[fx]=fy;

}

int getfather(int v)

{

if(f[v]==0)

{

return v;

}

else

{

f[v]=getfather(f[v]);

return f[v];

}

}

int main()

{

int i,j,x,y,tmp;

scanf("%d %d %d",&n,&m,&p);

for(i=1;i

题解

283 条题解

家族

信息

状态

开发

支持

题解

283 条题解

家族

信息

状态

开发

支持

还没有账户？

登录