Description

Z 国坐落于遥远而又神奇的东方半岛上,在小Z 的统治时代公路成为这里主要的交通手段。Z 国共有n 座城市,一些城市之间由双向的公路所连接。非常神奇的是Z 国的每个城市所处的经度都不相同,并且最多只和一个位于它东边的城市直接通过公路相连。Z 国的首都是Z 国政治经济文化旅游的中心,每天都有成千上万的人从Z 国的其他城市涌向首都。 为了使Z 国的交通更加便利顺畅,小Z 决定在Z 国的公路系统中确定若干条规划路线,将其中的公路全部改建为铁路。 我们定义每条规划路线为一个长度大于1 的城市序列,每个城市在该序列中最多出现一次,序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且,每个城市最多只能出现在一条规划路线中,也就是说,任意两条规划路线不能有公共部分。 当然在一般情况下是不可能将所有的公路修建为铁路的,因此从有些城市出发去往首都依然需要通过乘坐长途汽车,而长途汽车只往返于公路连接的相邻的城市之间,因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首都。 我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的次数,而Z 国的交通系统的“不便利值”为所有城市的不便利值的最大值,很明显首都的“不便利值”为0。小Z 想知道如何确定规划路线修建铁路使得Z 国的交通系统的“不便利值”最小,以及有多少种不同的规划路线的选择方案使得“不便利值”达到最小。当然方案总数可能非常大,小Z 只关心这个天文数字mod Q 后的值。 注意:规划路线1-2-3 和规划路线3-2-1 是等价的,即将一条规划路线翻转依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案。
Input

第一行包含三个正整数N、M、Q,其中N 表示城市个数,M 表示公路总数,N 个城市从1~N 编号,其中编号为1 的是首都。Q 表示上文提到的设计路线的方法总数的模数。接下来M 行,每行两个不同的正数ai、bi (1≤ ai , bi ≤ N)表示有一条公路连接城市ai 和城市bi。 输入数据保证一条公路只出现一次。
Output

包含两行。第一行为一个整数,表示最小的“不便利值”。 第二行为一个整数,表示使“不便利值”达到最小时不同的设计路线的方法总数 mod Q 的值。如果某个城市无法到达首都,则输出两行-1。
Sample Input
5 4 100
1 2
4 5
1 3
4 1
Sample Output
1
10
HINT

以下样例中是10 种设计路线的方法: (1) 4-5 (2) 1-4-5 (3) 4-5, 1-2 (4) 4-5, 1-3 (5) 4-5, 2-1-3 (6) 2-1-4-5 (7) 3-1-4-5 (8) 1-4 (9) 2-1-4 (10) 3-1-4 【数据规模和约定】对于20%的数据,满足N,M ≤ 10。对于50%的数据,满足N,M ≤ 200。对于60%的数据,满足N,M ≤ 5000。对于100%的数据,满足1 ≤ N,M ≤ 100000,1 ≤ Q ≤ 120000000。

树dp(首先判断是否连通),因为最后的方案不一定要所有的都选最优方案,所以dp[i][j][k]表示以节点i为根,不便利值不大于j,节点i向儿子连了k条边的方案数(k=0,1,2)

我们很轻易的想到了下面这个方程(借将狼踩尽的图)

关键是这个肯定超时,所以要优化(每搜索一个儿子做一遍,初始f[i,j,0]=1)

我是这样理解的,其实相当于每次加上一个儿子,然后更新f的值(这样应该很清楚吧)

 const
maxn=;
var
f:array[..maxn,-..,..]of int64;
first,next,last:array[..maxn*]of longint;
flag:array[..maxn]of boolean;
n,m,tot:longint;
q:int64; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; procedure init;
var
i,x,y:longint;
begin
read(n,m,q);
if m<>n- then
begin
writeln(-);
writeln(-);
halt;
end;
for i:= to m do
begin
read(x,y);
insert(x,y);
insert(y,x);
end;
end; function get(x:int64):int64;
begin
if (x>) and (x mod q=) then exit(q);
exit(x mod q);
end; procedure dfs(x:longint);
var
i,j:longint;
f1,f2:int64;
begin
j:=first[x];
flag[x]:=true;
for i:= to do
f[x,i,]:=;
while j<> do
begin
if flag[last[j]]=false then
begin
dfs(last[j]);
for i:= to do
begin
f1:=f[last[j],i,]+f[last[j],i,];
f2:=f[last[j],i-,]+f[last[j],i-,]+f[last[j],i-,];
f[x,i,]:=get(f[x,i,]*f2+f[x,i,]*f1);
f[x,i,]:=get(f[x,i,]*f2+f[x,i,]*f1);
f[x,i,]:=get(f[x,i,]*f2);
end;
end;
j:=next[j];
end;
end; procedure work;
var
i:longint;
begin
dfs();
for i:= to do
if f[,i,]+f[,i,]+f[,i,]> then
begin
writeln(i);
writeln((f[,i,]+f[,i,]+f[,i,])mod q);
exit;
end;
writeln(-);
writeln(-);
end; begin
init;
work;
end.

最新文章

  1. 强联通 HDU 2767 3836
  2. 在 C++ 代码中使用 UE4 插件---Using a plugin in C++ code
  3. 用shell脚本切分task_list,并分别执行的脚本
  4. css3学习总结6--CSS3字体
  5. MSSQL删除字段时出现 服务器: 消息 5074,级别 16,状态 1,行 1 的解决办法
  6. HDU 5773 The All-purpose Zero 求LIS
  7. iOS - 移动设备防丢失App
  8. VMware Workstation不能启用虚拟设备floppy0由于灭有相应的有效设备在主机上. 你要尝试在每次打开虚拟机电源时连接此虚拟设备?
  9. 做好织梦dedecms安全防护全部方法
  10. BZOJ 1901 Zju2112 Dynamic Rankings
  11. AOP的相关概念
  12. 理解 OAuth2.0
  13. RecyclerView联动滑动失败
  14. python3下最简单的九九乘法表
  15. index.php入口文件至根目录
  16. Android-获取Html元素
  17. Vue学习之路6-条件渲染
  18. 服务器部署全程记录(centos6.5)
  19. Python-递归、三元表达式列表生成式等
  20. 关于T-SQL中exists或者not exists子查询的“伪优化”的做法

热门文章

  1. office2013 win 32bit (含激活工具)
  2. 小技巧之a标签自动解析URL
  3. ubuntu共享文件夹给virtualbox
  4. django 学习-3 模板变量
  5. Linux命令(4):cat命令
  6. web服务器顺带网络负载均衡
  7. Oracle学习第二天---Profile的使用
  8. 163免费邮客户端设置的POP3、SMTP、IMAP地址
  9. wpf DataGrid 双击获取当前行的控件
  10. thinkphp3.2引入php 实例化类