bzoj1063: [Noi2008]道路设计

本文主要是介绍bzoj1063: [Noi2008]道路设计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1063

思路：首先m<n-1肯定不连通，先写个特判。

设f[i][j][k]表示以i为根的子树中，最大不便利值为j（到i的最多经过的公路条数），i向儿子连了k条铁路（k=0,1,2）的方案数

然后就是最关键的一步了。

j<log3(n)

这有些类似树链剖分，如果用树链剖分的想法，那么可证j<log2(n)，其实也已经可以做了。

具体可以证明在3叉树时达到上限log3(n)，可以自己画图看一下。

然后DP方程及转移就出来了：

设当前点为x，v是x的儿子

令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]

f1不向这个儿子建铁路，f2向这个儿子建铁路 

f[x][j][2]=f[x][j][2]*f1+f[x][j][1]*f2

f[x][j][1]=f[x][j][1]*f1+f[x][j][0]*f2

f[x][j][0]=f[x][j][0]*f1

然后从小到大，0-log3（n）扫一遍，有方案就输出即可

#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=100010,maxm=200010,lim=10;
typedef long long ll;
using namespace std;
int pre[maxm],now[maxn],son[maxm],tot;
int n,m,Q;ll f[maxn][12][3];//i的子树，子树内最大不便利值为j，向儿子修的铁路条数k方案数。 
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
int get(ll t){return !t?0:t%Q?t%Q:Q;}//如果方案数%Q==0就设为Q，不能直接设为0，否则会被当成没有方案 void dfs(int x,int fa){int cnt=0;for (int y=now[x];y;y=pre[y]) if (son[y]!=fa) dfs(son[y],x),cnt++;for (int i=0;i<=lim;i++) f[x][i][0]=1;if (!cnt) return;for (int y=now[x];y;y=pre[y]) if (son[y]!=fa){int v=son[y];for (int j=0;j<=lim;j++){ll t,f1=!j?0:f[v][j-1][0]+f[v][j-1][1]+f[v][j-1][2],f2=f[v][j][0]+f[v][j][1];//f1不向这个儿子建铁路，f2向这个儿子建铁路 t=(ll)f[x][j][2]*f1+(ll)f[x][j][1]*f2;f[x][j][2]=get(t);t=(ll)f[x][j][1]*f1+(ll)f[x][j][0]*f2;f[x][j][1]=get(t);t=(ll)f[x][j][0]*f1;f[x][j][0]=get(t);}}
}int main(){scanf("%d%d%d",&n,&m,&Q);for (int i=1,a,b;i<=m;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);if (m<n-1){puts("-1\n-1");return 0;}dfs(1,0);ll sum;for (int i=0;i<=lim;i++) if (sum=f[1][i][0]+f[1][i][1]+f[1][i][2]) return printf("%d\n%d\n",i,(int)sum%Q),0;return 0;
}

这篇关于bzoj1063: [Noi2008]道路设计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---