NOI 2008 设计路线 design

基本方法

首先，注意一个重要的条件“每个城市最多只和一个位于它东边的城市相连”，通过这个条件，必须能够明白这个国家的公路网其实是树（或森林）。为什么是树？我们知道，树中除了根其余节点都有且只有一个父节点，假设每个城市东边的城市就是它的父节点，恰好满足是树的条件。把城市1当作根节点，如果每个节点都有到达根节点1的路径，那么肯定只有一棵树，如果图中有多个连通分量，那么是无解的，输出两个-1。另外对于这道题，由于数据可以保证不存在环，只需判断M是否为N-1即可。

明白这是一棵树以后，问题就清晰多了。问题可以被描述为：给定一个根节点为1的数要求在树中找到一些不相交的链，使得每个节点的不便利值的最大值最小，并求出满足条件的方案个数。一个节点的不便利值就是从该节点到根的路径上经过的非链边的条数。

先考虑第一问，求最小不便利值。在纸上随意画几棵树，算出最小不便利值，可以发现很难使最小不便利值很大。当根节点至少有三个子节点时，才能使不便利值为1，而第二层的节点再都至少有三个子节点，才能使不便利值为2。可以发现，只有节点个数至少为一个高度为k+1的满三叉树，才能使不便利值达到k，反证法很容易证明。对于最大的数据N<=100000，也不过最多可能有10层满三叉树，最大达到的不便利值为9。发现第一问的可能值很少，可以考虑和第二问共同解决。可以知道，使得方案数大于0的最小不便利值B，一定为结果。于是可以从0开始枚举第一问的答案，计算方案数，直到方案数大于0。

解决第二问，需要用到树形动态规划。考虑每个子树根节点向下连边构造不相交链，它向下连边有3种可能，不连边，只连一条边，只连两条边。不可能连更多，否则就会出现相交的链，连两条边还必须满足它的父节点没有向它连边。据此定义：

F[i,b]为以i为根的子树中，每个节点相对于子树的根最大不便利值不超过b，且子树根节点向下连两条边的方案个数。
G[i,b]为以i为根的子树中，每个节点相对于子树的根最大不便利值不超过b，且子树根节点向下连一条边或不连边的方案个数。
对于F[i,b] (b>0)
- 当i有1个或0个子节点
- F[i,b]=0
当i有至少2个子节点
- F[i,b]=Σ(G[j,b]*G[k,b]*Π(F[l,b-1]+G[l,b-1])) (j,k,l为i的不同的子节点)
对于G[i,b] (b>0)
- 当i有0个子节点
- G[i,b]=1
当i有至少1个子节点
- G[i,b]=Σ(G[j,b]*Π(F[l,b-1]+G[l,b-1])) + Π(F[l,b-1]+G[l,b-1]) (j,l为i的不同的子节点)

特殊地，当b为0时

对于F[i,b]
- 当i有且只有2个子节点
- F[i,b]=G[j,b]*G[k,b] (j和k为i的不同的子节点)
当i有多于或少于2个子节点
- F[i,b]=0
对于G[i,b]
- 当i没有子节点
- G[i,b]=1
当i有且只有1个子节点
- G[i,b]=G[j,b] (j为i的子节点)
当i有多余1个子节点
- G[i,b]=0

时间复杂度为O(N^3logN)。根据上述所有的方程，直接进行树形动态规划，可以拿到40~50分。观察N的范围(N<=100000)，要想全部通过，必须优化到O(NlogN)，向着这个目标，开始着手优化。

状态转移优化

F[i,b]=Σ(G[j,b]*G[k,b]*Π(F[l,b-1]+G[l,b-1])) (j,k,l为i的不同的子节点)
G[i,b]=Σ(G[j,b]*Π(F[l,b-1]+G[l,b-1])) + Π(F[l,b-1]+G[l,b-1]) (j,l为i的不同的子节点)

再次观察上述两个方程，发现大部分时间浪费在这里，尤其是Π(F[l,b-1]+G[l,b-1])，重复计算了很多次。是否可以把它先计算出呢？我的第一想法就是设置一个变量记录，令W=Π(F[l,b-1]+G[l,b-1]) (l为i的所以子节点)。在计算G[i,b]的Σ内部时，由于每次Π(F[l,b-1]+G[l,b-1])都少乘一个(F[j,b-1]+G[j,b- 1])，而多乘一个G[j,b]，结果是W/(F[j,b-1]+G[j,b-1])*G[j,b]。但这种想法是错误的，首先(F[j,b- 1]+G[j,b-1])可能为0，除法不可用，就算不为0，由于结果要求一个mod Q以后的值，除法会破坏同余的性质。由于式子庞大而繁杂，不利于思考，我把它变换形式后思考。

对于给定的i,b，设节点i有V个子节点，定义

A[i]=F[j,b-1]+G[j,b-1] (j为节点i的子节点 A[i]为一个连续的数组 (1<=i<=V) )
B[i]=G[j,b] (j,k为节点i的两个不同子节点 B[i]为一个连续的数组 (1<=i<=V) )
R0=Π(A[i]) (1<=i<=V)
R1=Σ(B[i]*Π(A[j])) (1<=i,j<=V ,i!=j)
R2=Σ(B[i]*B[j]*Π(A[k])) (1<=i,j,k<=V ,i!=j ,i!=k ,j!=k)

则F[i,b]=R2，G[i,b]=R0+R1

我们的目的是要在线性的时间内求出R0,R1,R2，需要定义辅助的线性表。

设sf[i]为A[i]的从第i项开始的后缀之积，则有
- sf[V]=A[V]
sf[i]=sf[i+1]*A[i] (1<=i<=V-1)
设pf[i]为A[i]的以第i项为尾的前缀之积，则有
- pf[0]=1
pf[i]=pf[i-1]*A[i] (1<=i<=V)

显然，R0=pf[V]。求R1线性时间的方法不难想到，R1就是表A中去除第i个元素换成B[i]的所有的和，对于一个给定的i，只需加上 pf[i-1]*B[i]*sf[i+1]，就可以实现线性时间的求和。而求R2看似与求R1类似，却要取出两个元素替换，不易想出线性时间的方法。由于要取两个元素，考虑固定第一个位置，第二个元素位置变化的和就与求R1类似了。

定义C[i]为以第i项为开头的所有替换的后缀积之和。

定义式为 C[i]=Σ(B[j]*Π(A[k])) (1<=i,j,k<=C ,i<=j,i<=k,j!=k)

为了快速求出所有C[i]，发现C[i]与C[i+1]之间有递推关系

C[V]=B[V]
C[i]=C[i+1]*A[i] + B[i]*sf[i+1]

于是可以在线性时间内求出了C。同时很方便，R1=C[1]。

R2=Σ(pf[i-1]*B[i]*C[i+1]) (1<=i<=N-1)，也可以在线性时间内求出了。

经过上述优化，每次状态转移就成了O(V)，而每个节点被访问一次，所以总的时间复杂度为O(N*logN)，理论上可以拿到满分了。但是还有一下细节不容忽视，如果方案数不为0，而Mod Q以后恰为0了，此时枚举应该中止了，但却没有，怎么办。我的方法是增设了两个数组，记录F[i,b]和G[i,b]的每项是否为“真正的0”(区别于 mod以后的0)，在状态转移的处理中较为麻烦，但是可以判断了。

这是NOI2008相对较简单的一道题了，NOI上有6位大牛拿到了满分，而且平均分高达21.122。但是对于包括我在内的大多数人来说，做出这道题依然很不容易。

/* 
 * Problem: NOI2008 design
 * Author: Guo Jiabao
 * Time: 2009.3.4 22:18
 * State: Solved
 * Memo: 树形动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=100001,MAXD=10;
typedef long long big;
using namespace std;
struct edge
{
	edge *next;
	int t;
}ES[MAXN*2];
struct vertex
{
	edge *f;
	int cnt;
}V[MAXN];
int N,M,MOD,MinB=-1,Total=-1,EC=-1;
big F[MAXN][MAXD],G[MAXN][MAXD];
big A[MAXN],B[MAXN],pf[MAXN],sf[MAXN],C[MAXN];
big R0,R1,R2;
bool ZF[MAXN][MAXD],ZG[MAXN][MAXD],ZA[MAXN],ZB[MAXN],ZC[MAXN],Zsf[MAXN],Zpf[MAXN],ZR0,ZR1,ZR2;
void dp(int i,int b);
inline void addedge(int a,int b)
{
	ES[++EC].next=V[a].f;
	(V[a].f=&ES[EC])->t=b;
	V[a].cnt++;
}
void maketree(int i,int f)
{
	edge *k,*p;
	if (V[i].f->t==f)
		V[i].f=V[i].f->next,V[i].cnt--;
	for (k=V[i].f;k;p=k,k=k->next)
		if (k->t==f)
			p->next=k->next,V[i].cnt--;
		else
			maketree(k->t,i);
}
bool init()
{
	freopen("design.in","r",stdin);
	freopen("design.out","w",stdout);
	scanf("%d%d%d",&N,&M,&MOD);
	if (M!=N-1) return false;
	for (int i=1;i<=M;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b); addedge(b,a);
	}
	maketree(1,0);
	return true;
}
void clear()
{
	for (int i=1;i<=N;i++)
		for (int j=0;j<MAXD;j++)
			F[i][j]=G[i][j]=-1;
}
void cFG(int i,int b,big F[][MAXD],big G[][MAXD],int MOD)
{
	int j,cnt;
	edge *e;
	ZR0=false;
	for (cnt=0,e=V[i].f;e;e=e->next)
	{
		j=e->t;
		A[++cnt]=F[j][b-1]+G[j][b-1]%MOD;
		ZA[cnt]=ZF[j][b-1]&&ZG[j][b-1];
		ZR0|=ZA[cnt];
		B[cnt]=G[j][b];
		ZB[cnt]=ZG[j][b];
	}
	pf[0]=1;
	Zpf[0]=false;
	for (j=1;j<=cnt;j++)
	{
		pf[j]=pf[j-1]*A[j]%MOD;
		Zpf[j]=Zpf[j-1]||ZA[j];
	}
	R0=pf[cnt];
	sf[cnt]=A[cnt];
	Zsf[cnt]=ZA[cnt];
	for (j=cnt-1;j>=1;j--)
	{
		sf[j]=sf[j+1]*A[j]%MOD;
		Zsf[j]=Zsf[j+1]||ZA[j];
	}
	C[cnt]=B[cnt];
	ZC[cnt]=ZB[cnt];
	for (j=cnt-1;j>=1;j--)
	{
		C[j]=(C[j+1]*A[j]%MOD + B[j]*sf[j+1]%MOD)%MOD;
		ZC[j]=(ZC[j+1]||ZA[j] && B[j]||sf[j+1]);
	}
	R1=C[1];R2=0;
	ZR1=ZC[1];
	ZR2=true;
	for (j=1;j<cnt;j++)
	{
		R2+=((pf[j-1]*B[j])%MOD*C[j+1])%MOD;
		R2%=MOD;
		ZR2&=(Zpf[j-1] || ZB[j] || ZC[j+1]);
	}
}
void prepare(int i,int b)
{
	int l;
	edge *e;
	for (e=V[i].f;e;e=e->next)
	{
		l=e->t;
		if (F[l][b-1]==-1) dp(l,b-1);
		if (F[l][b]==-1) dp(l,b);
	}
}
void dp(int i,int b)
{
	int j,k;
	if (b==0)
	{
		if (V[i].cnt==2)
		{
			j=V[i].f->t;k=V[i].f->next->t;
			if (G[j][b]==-1) dp(j,b);
			if (G[k][b]==-1) dp(k,b);
			F[i][b]=G[j][b]*G[k][b]%MOD;
			ZF[i][b]=ZG[j][b]||G[k][b];
		}
		else
		{
			F[i][b]=0;
			ZF[i][b]=true;
		}
		if (V[i].cnt==1)
		{
			j=V[i].f->t;
			if (G[j][b]==-1) dp(j,b);
			G[i][b]=G[j][b];
			ZG[i][b]=ZG[j][b];
		}
		else if (V[i].cnt==0)
			G[i][b]=1;
		else
		{
			G[i][b]=0;
			ZG[i][b]=true;
		}
	}
	else
	{
		if (V[i].cnt==0)
			G[i][b]=1;
		else
			prepare(i,b);
		cFG(i,b,F,G,MOD);
		if (V[i].cnt<=1)
		{
			F[i][b]=0;
			ZF[i][b]=true;
		}
		else
		{
			F[i][b]=R2;
			ZF[i][b]=ZR2;
		}
		if (V[i].cnt>0)
		{
			G[i][b]=(R0+R1)%MOD;
			ZG[i][b]=ZR0 && ZR1;
		}
	}

}
void solve()
{
	clear();
	for (MinB=0;;MinB++)
	{
		dp(1,MinB);
		int t1=(F[1][MinB] + G[1][MinB])%MOD;
		if (t1==0 && ZF[1][MinB] && ZG[1][MinB]) continue;
		Total=t1;
		return;
	}
}
int main()
{
	if (init())
		solve();
	printf("%dn%dn",MinB,Total);
	return 0;
}

<div class="MainText">

【问题描述】

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 是等价的，即将一条规划路线翻转依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案。

【输入格式】

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

【输出格式】

输出文件应包含两行。第一行为一个整数，表示最小的“不便利值”。 第二行为一个整数，表示使“不便利值”达到最小时不同的设计路线的方法总数 mod Q 的值。
如果某个城市无法到达首都，则输出两行-1。

【输入样例】

5 4 100
1 2
4 5
1 3
4 1
【输出样例】
1
10
【样例说明】
以下样例中是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。</div>

上次修改时间 2017-02-03

基本方法

状态转移优化

相关日志