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

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

Posted by shinekai at 2010-02-07 13:13:40 on Problem 3177
首先这道题有重边,如
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]时就错了。。这个现在也不解。。

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