poj 3417 Network 题解
标签：节点 const ons color soft ros 思路 for include
题意：
先给出一棵树，然后再给出m条边，把这m条边连上，然后剪掉两条边，一条是原边，一条是新边，问有多少种方案能使图不连通。
思路：
从原边的角度看
1.树加边，一定成环，加一条(u,v)边就有u->lca->v上的边被覆盖一次
2.当一条边没被覆盖时，删去该边与任意一条新边都能使图不连通，即有m种方案
3.当一条边被覆盖1次时，删去与该边成环的新边，即有1种方案
4.当一条边被覆盖1次以上时，没有方案
用树形dp，dp[i]表示第i号点与其父亲相连的边被覆盖的次数。一条新边(u,v)加入则++dp[u],++dp[v],dp[lca(u,v)]-=2，计算时从叶子结点向上累加，子节点的值加到父节点上，最后每个节点上的值就是覆盖次数。
反思：
1.倍增求lca时不熟练。
2.计算时根节点不计算。
代码：
1 #include 2 const int M=100005;
3 #define swap(x,y) t=x,x=y,y=t
4 int t,cnt,ans,v[M1],dp[M],dep[M],hea[M1],nex[M1],p[M][18];
5
6 int read()
7 {
8 int x=0; char ch=getchar();
9 while (ch48 || ch>57) ch=getchar();
10 while (ch>47 && ch58) x=(x1)+(x3)+ch-48,ch=getchar();
11 return x;
12 }
13
14 void add(int x,int y) { v[++cnt]=y,nex[cnt]=hea[x],hea[x]=cnt; }
15
16 void dfs(int u,int x)
17 {
18 dep[u]=dep[p[u][0]=x]+1;
19 for (int i=hea[u];i;i=nex[i])
20 if (v[i]^x) dfs(v[i],u);
21 }
22
23 int lca(int x,int y)
24 {
25 if (dep[x]dep[y]) swap(x,y);
26 for (int i=17;~i;--i)
27 if (dep[p[x][i]]>=dep[y]) x=p[x][i];
28 if (x==y) return x;
29 for (int i=17;~i;--i)
30 if (p[x][i]^p[y][i]) x=p[x][i],y=p[y][i];
31 return p[x][0];
32 }
33
34 void DFS(int u,int x)
35 {
36 for (int i=hea[u],y;y=v[i],i;i=nex[i])
37 if (y^x) DFS(y,u),dp[u]+=dp[y];
38 }
39
40 int main()
41 {
42 int n=read(),m=read(),x,y,i,j;
43 for (i=1;iread(),add(x,y),add(y,x);
44 dfs(1,0);
45 for (i=1;i18;++i)
46 for (j=1;jj)
47 if (p[j][i-1]) p[j][i]=p[p[j][i-1]][i-1];
48 for (i=1;i2;
49 DFS(1,0);
50 for (i=2;ii)
51 if (!dp[i]) ans=ans+m;
52 else if (dp[i]==1) ++ans;
53 printf("%d\n",ans);
54 return 0;
55 }
poj 3417 Network 题解
标签：节点 const ons color soft ros 思路 for include
原文地址：http://www.cnblogs.com/HHshy/p/7189574.html
评论