首页 > 代码库 > poj 3417 Network （LCA，路径上有值）
poj 3417 Network （LCA，路径上有值）
题意：
N个点，构成一棵树。给出这棵树的结构。
M条边，(a1,b1)...(am,bm)，代表给树的这些点对连上边。这样就形成了有很多环的一个新”树“。
现在要求你在原树中断一条边，在M条边中断一条边，使得新”树“被分成两个部分。
问有多少种方案。
思路：
连上某条新边（a,b），则必定形成一个环。环的路径是a->...->lca(a,b)->...->b，给这些边的值都加1 。
分情况：
在原树中，若一条边的值>=2，去掉这条边，再去掉M条边中的一条，不影响原树的连通性。方案数为0。
若一条边的值==1，去掉这条边，必须去掉这条边所在环的那条新边（M条边之一）。方案数为1。
若一条边的值==0，去掉这条边，再随意去掉M条边中的一条，都会破坏原树的连通性。方案数为M。
在计算边的值时，采用DP的方式，若要将路径a->...->lca(a,b)->...->b上的边值都加1，则dp[a]++,dp[b]++,dp[lca(a,b)]-=2。
直接看代码。
代码：
int const maxn = 100005;struct node{ int to,next,lca;};int fa[maxn];bool vis[maxn];int head[2*maxn];int qhead[2*maxn];node edge[maxn*2];node qedge[maxn*2];int n,m,cnt1,cnt2,cn;int dp[maxn], edgeCount[maxn];inline void Addedge(int u,int v){ edge[++cnt1].to=v; edge[cnt1].next=head[u]; head[u]=cnt1; edge[++cnt1].to=u; edge[cnt1].next=head[v]; head[v]=cnt1;}inline void Addqedge(int u,int v){ qedge[++cnt2].to=v; qedge[cnt2].next=qhead[u]; qhead[u]=cnt2; qedge[++cnt2].to=u; qedge[cnt2].next=qhead[v]; qhead[v]=cnt2;}void init(){ mem(head,-1); mem(qhead,-1); mem(vis,false); rep(i,1,n) fa[i]=i; cnt1=cnt2=0;}int findFa(int x){ return fa[x]==x?x:fa[x]=findFa(fa[x]);}void Tarjan_LCA(int u){ fa[u]=u; vis[u]=true; for(int i=head[u];i!=-1;i=edge[i].next){ if(!vis[edge[i].to]){ Tarjan_LCA(edge[i].to); fa[edge[i].to]=u; } } for(int i=qhead[u];i!=-1;i=qedge[i].next){ if(vis[qedge[i].to]) qedge[i].lca=findFa(qedge[i].to); }}int dfsDp(int u,int fa){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa) continue; int t1=dfsDp(v,u); edgeCount[++cn]=t1; dp[u]+=t1; } return dp[u];}int a,b;int main(){ while(scanf("%d%d",&n,&m)!=EOF){ init(); rep(i,1,n-1){ scanf("%d%d",&a,&b); Addedge(a,b); } mem(dp,0); rep(i,1,m){ scanf("%d%d",&a,&b); Addqedge(a,b); dp[a]++; dp[b]++; } Tarjan_LCA(1); for(int i=1;i<=cnt2;i+=2){ dp[qedge[i].lca]-=2; } mem(edgeCount,0); cn=0; dfsDp(1,-1); int ans=0; rep(i,1,cn){ if(edgeCount[i]==1) ans++; else if(edgeCount[i]==0) ans+=m; } printf("%d\n",ans); }}
poj 3417 Network （LCA，路径上有值）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。