首页 > 代码库 > BZOJ 1718: [Usaco2006 Jan] Redundant Paths 分离的路径
BZOJ 1718: [Usaco2006 Jan] Redundant Paths 分离的路径
Description
为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．
每对草场之间已经有至少一条路径．给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．
Input
第1行输入F和R，接下来R行，每行输入两个整数，表示两个草场，它们之间有一条道路．
Output
最少的需要新建的道路数．
题解：
题目要求新建最少的边,使得整个图只有一个边双联通分量.
把图用双联通分量缩点后会形成一个DAG,其中这个DAG上的叶子节点可以亮亮互相配对连边.
是最优情况.
所以ans=ceil(leaf/2)=(leaf+1)/2
代码：
#include<cstdio>#include<algorithm>using namespace std;int H[5005],X[20005],P[20005],tot,_tot,num[20005],fa[20005];bool iscut[20005];inline void add(int x,int y){ P[++tot]=y;X[tot]=H[x];H[x]=tot;num[tot]= ++_tot; P[++tot]=x;X[tot]=H[y];H[y]=tot;num[tot]=_tot;}int x,y,n,m;int low[5005],dfn[5005],cnt,point[5005],tim,stk[5005],top;void tarjan(int u){ low[u]=dfn[u]=++tim; stk[top++]=u; for(int i=H[u];i;i=X[i]){ if(num[i]==fa[u]) continue; if(!dfn[P[i]]){ fa[P[i]]=num[i]; tarjan(P[i]); low[u]=min(low[P[i]],low[u]); }else{ low[u]=min(dfn[P[i]],low[u]); } } if(low[u]==dfn[u]){ int k;++cnt; do{ k=stk[--top]; point[k]=cnt; }while(k!=u); }}bool vis[20005];int in[5005];int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); add(x,y); } tarjan(1); for(int i=1;i<=n;i++){ for(int j=H[i];j;j=X[j]){ if(vis[j]) continue; if(point[i]==point[P[j]]) continue; in[point[i]]++;in[point[P[j]]]++; vis[j]=1; } } int leaf=0; for(int i=1;i<=cnt;i++){ if(in[i]==2) leaf++; } printf("%d",(leaf+1)>>1); return 0;}
BZOJ 1718: [Usaco2006 Jan] Redundant Paths 分离的路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。