首页 > 代码库 > bzoj1063【Noi2008】道路设计
bzoj1063【Noi2008】道路设计
题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1063
用一种划分方式将树划为重链和轻链,使得所有点到根节点的路径经过的轻链最大值最小
sol: 先判定图是否联通,若不连通输出-1
考虑树形dp,f[i][j]表示以i为根的字树中到i的最大不便利值为j的方案数
然而这时空都是O(n^2)的QAQ,而且没法转移
考虑运用树链剖分的思想可证明,j之多为O(log2(n))的
事实上,j在图为完全二叉树时取最大值O(log3(n))
对于转移,f[i][j][k]表示以i为根值为j,i向儿子连了k条边的方案数
则对于每个节点u,可以选择向(f1)或不向(f2)其某个儿子v连边
则f1=f[v][j-1][0]+f[v][j-1][1]+f[v][j-1][2] (不向儿子连边)
f2=f[v][j][0]+f[v][j][1] (向儿子连边)
对于某个点,在遍历到他的一个儿子时,之前儿子的影响已经被累加进答案f[u][j][]
考虑新加进来的点的影响(为避免后效性应按2-1-0的顺序计算):
f[u][j][2]=f[u][j][2]*f1+f[u][j][1]*f2
f[u][j][1]=f[u][j][1]*f1+f[u][j][0]*f2
f[u][j][0]=f[u][j][0]*f1
最后从小到大扫一遍j,如果有,输出即可,注意%Q等于0的情况(设为Q)
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Mx=200010; int n,m,Q,tot,head[Mx],ver[Mx],next[Mx]; long long ans,f[Mx][12][3]; inline long long jud(long long tmp)//处理%Q=0的情况 { if(tmp!=0&&tmp%Q==0) return Q; else return tmp%Q; } inline void add(int x,int y) { tot++; next[tot]=head[x]; ver[tot]=y; head[x]=tot; } void dfs(int x,int fa) { int cnt=0;//cnt记录儿子个数 for(int i=head[x];i;i=next[i]) if(ver[i]!=fa) dfs(ver[i],x),cnt++; for(int j=0;j<=10;j++) f[x][j][0]=1;//f数组赋初值 if(cnt==0) return ;//叶子节点 for(int i=head[x];i;i=next[i])//树形dp if(ver[i]!=fa) { int y=ver[i]; for(int j=0;j<=10;j++) { long long f1,f2; f1=f[y][j-1][0]+f[y][j-1][1]+f[y][j-1][2]; f2=f[y][j][0]+f[y][j][1]; f[x][j][2]=jud((long long) f[x][j][2]*f1+(long long) f[x][j][1]*f2); f[x][j][1]=jud((long long) f[x][j][1]*f1+(long long) f[x][j][0]*f2); f[x][j][0]=jud((long long) f[x][j][0]*f1); } } } int main() { scanf("%d%d%d",&n,&m,&Q); for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); add(x,y); add(y,x); } if(m<n-1) { puts("-1\n-1"); return 0; } dfs(1,0); for(int j=0;j<=10;j++) { ans=f[1][j][0]+f[1][j][1]+f[1][j][2]; if(ans!=0) { cout<<j<<endl<<(ans%Q)<<endl; return 0; } } return 0; }
bzoj1063【Noi2008】道路设计
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。