- 浏览: 35792 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Problem Description
上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。
Input
输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。
Output
对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出"Yes",否则输出"No"。
Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Sample Output
Yes Yes No 其实就系一条判断一副图系唔系树ge问题,一黎就捻到判断方法,数据结构为并查集,果断认为系水题: 点数-1==边数 && 只有一颗树 但系错左n次……先搵到一个奇怪ge错误,印象深刻,所以先写尼条题!!!!!OTZ 真系好鬼死奇怪……结合代码讲。 hdu 1727 46ms 1132K 1568B Pascal SGetEternal{(。)(。)}!
_______________________________无痛阉割线___________________________________
其实就系只需要判断 是否只有一颗树+点数-1是否等于边数ge问题…………
本来系一条水题,但系就系比d奇怪ge错误搞死左n次!!!!
我犯左一个非常蛋疼ge错误!!!!!!!
如果将Union里面ge 关于rank比较改成x,y比较就会WA。点解…………
上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。
Input
输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。
Output
对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出"Yes",否则输出"No"。
Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Sample Output
Yes Yes No 其实就系一条判断一副图系唔系树ge问题,一黎就捻到判断方法,数据结构为并查集,果断认为系水题: 点数-1==边数 && 只有一颗树 但系错左n次……先搵到一个奇怪ge错误,印象深刻,所以先写尼条题!!!!!OTZ 真系好鬼死奇怪……结合代码讲。 hdu 1727 46ms 1132K 1568B Pascal SGetEternal{(。)(。)}!
var i,u,v,max,min,edge,node,tree : longint; father,rank:array[0..100000] of longint; exsi: array[0..100000] of boolean; function Maxi(a,b:longint):longint; begin if a>b then Maxi:=a else Maxi:=b; end; function Mini(a,b:longint):longint; begin if a<b then Mini:=a else Mini:=b; end; function Find(x:longint):longint; //压缩路径(其实就系将集合ge所有元素指向标记集合元素) begin if x<>father[x] then father[x]:=Find(father[x]); Find:=father[x]; end; procedure Union(x,y:longint); //合并集合(就系呢度发生悲剧) begin x:=Find(x); y:=Find(y); if x=y then exit; if rank[x]<rank[y] then father[x]:=y //就系呢度!!!!如果将rank[x]<rank[y]改成x<y就会WA!!!!! else begin if rank[x]=rank[y] then inc(rank[x]); //仲有呢度。 father[y]:=x; end; end; //真系老hi都捻唔到会错系呢度{-_____-}||| begin read(u,v); while (u<>-1) or (v<>-1) do begin for i:=1 to 100000 do father[i]:=i; //老豆数组初始化………… fillchar(rank,sizeof(rank),0); //秩数组初始化……………… fillchar(exsi,sizeof(exsi),false); //判断结点存在ge数组初始化……………… tree:=0; edge:=0; node:=0; //tree系树棵树,edge系边数,node系结点数。 min:=100001; max:=-1; //优化,确定结点范围min~max。 while (u<>0) or (v<>0) do begin if (u<>v) then begin //如果u=v就吾做啦。 inc(edge); //加边…… exsi[u]:=true; exsi[v]:=true; max:=Maxi(max,Maxi(u,v)); min:=Mini(min,Mini(u,v)); Union(u,v); end; read(u,v); end; for i:=min to max do if exsi[i]=true then begin //如果结点存在就判断…… if father[i]=i then inc(tree); //如果自己系自己老豆,就加一颗树。 inc(node); //加点 end; if ((node-1=edge) and (tree=1)) or ((max=-1) and (min=100001)) then writeln('Yes') //判断min同max系考虑左空树ge情况………… else writeln('No'); read(u,v); end; end.
_______________________________无痛阉割线___________________________________
其实就系只需要判断 是否只有一颗树+点数-1是否等于边数ge问题…………
本来系一条水题,但系就系比d奇怪ge错误搞死左n次!!!!
我犯左一个非常蛋疼ge错误!!!!!!!
如果将Union里面ge 关于rank比较改成x,y比较就会WA。点解…………
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1143Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 828What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1164Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 757find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 989Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 728box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 777Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 961Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1155二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 977Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 856Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 763Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1007分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1222Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1062Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 633Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 567find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 657N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 752Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 636开门人和关门人 Time Limit: 2000/1000 ...
相关推荐
算术(HDU-6715).rar
最短路(HDU-2544).rar
数字图像处理总ppt_hdu_许老师.pdf
算法-数塔(HDU-2084).rar
算法-确定比赛名次(HDU-1285).rar
高级计算机图形学_mm的_重点笔记_hdu_吴xy.pdf
经典算法:(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)
杭电的一些acm题目,都是我自己一个一个自己提交的
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
HarvestPlat.47hdu3u2t3.gazKzpN
SkyPlat.47hdu3u2t3.gaxdJY7
FarmersPlat.47hdu3u2t3.gaimWw2
IntervalPlat.47hdu3u2t3.ga6cFnt