Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:好不容易终于AC了,老是WA的人可以看下,不过现在还是很奇怪

Posted by treert at 2012-04-29 22:32:12 on Problem 3177
In Reply To:好不容易终于AC了,老是WA的人可以看下,不过现在还是很奇怪 Posted by:shinekai at 2010-02-07 13:13:40
> 首先这道题有重边,如
> 2 2
> 1 2
> 1 2
> 应该输出 1
> 2 2
> 1 2
> 2 1
> 同样应该输出 1
> 记得判断重边 BT的数据
> 同时当我用tarjan算法先算出所有的dfn[x]跟low[x]后,是利用下面的slove()解决的
> void slove()
> {
> 	int i,v;
> 	node* temp;
> 	for(i=1;i<=f;i++)//f是节点数
> 	{
> 		temp=edge[i].next;
> 		while(temp)//遍历每条边
> 		{
> 			v=temp->v;
> 			if(low[i]!=low[v])//一开始是利用dfn[i]<low[v],但是WA
> 			{
> 				cnt[low[i]]++;//cnt是记录出入度,等于1时表示是叶子节点
> 			}
> 			temp=temp->next;
> 		}
> 	}
> 	ans=0;
> 	for(i=1;i<=f;i++)
> 		if(cnt[i]==1)
> 			ans++;
> 	printf("%d\n",(ans+1)/2);//叶节点/2既是所需添加的最少边。
> }
> 
> 假如边(u,v),当low[u]!=low[v]时可以知道u跟v属于不同的双连通分支,也就是边(u,v)是桥。
> 但是觉得也可以利用dfn[u]<low[v]判断桥(也就是桥的正常判断方法),然后两端的连通分支的出入度加1,感觉思想跟上面low[u]!=low[v]是一样的,但是,low[u]!=low[v]时就AC了,但dfn[u]<low[v]时就错了。。这个现在也不解。。

low[u]!=low[v],似乎是无意义的,当low[u]!=low[v]时并不能得出u跟v属于不同的双连通分支

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator