Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:好不容易终于AC了,老是WA的人可以看下,不过现在还是很奇怪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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator