2023NOIP A层联测14 修路

题目大意

有一个有$n$个点$m$条边的无向连通图，第$i$条边连接点$u_i$和$v_i$，长度为$l_i$。

你想要求这个图的一棵生成树，并规定一个中心点$mid$。定义一种规划的拥挤指数为$k\times S+\sum _{i=1}^{n}dis(i,mid)$，其中有$k$表示只被一条边连接的点的数量，$dis(u,v)$表示点$u$到点$v$的距离，$S$为给定的常数。

求如何修建道路和规划中心点，才能使拥挤程度最小，以及有多少种方案（求生成树+规划中心点）能使拥挤程度最小。

$1\le n\le 15,n-1\le m\le \frac{n(n-1)}{2},0\le l_i,S\le 10^9$

时间限制$7000ms$，空间限制$1024MB$。

题解

我们枚举每个点，让它作为中心点，并找到一个拥挤程度最小的生成树。

我们发现$\sum _{i=1}^{n}dis(i,mid)$其实等于$\sum _{i=1}^{n}t{f}_i\times si{z}_i$，其中$le{n}_i$表示当$mid$为根时点$i$到父亲的距离，$si{z}_i$表示子树$i$的大小。

因为$n$比较小，我们可以使用状压$DP$。

设$f[i][s]$表示当前的根节点为$i$，$i$的子树中点的集合为$s$时的拥挤程度和方案数（要保存两个数，可以用结构体），$g[i][s]$表示当前根节点为$i$且根节点只有一个儿子，$i$的子树中（不包括$i$）的点的集合为$s$时的拥挤程度和方案数（其实就是一个连通块连出一条边到点$i$）。注意虽然根节点有可能只被一条边连接，但当$s$不为点的全集时，这里的$i$都不算入$k$中。

初始值为 f [ i ] [ 2 i − 1 ] = { 0 , 1 } f[i][2^{i-1}]=\{0,1\} f[i][2i−1]={0,1}，其余的$f$值和$g$值为 { + ∞ , 0 } \{+\infty,0\} {+∞,0}。其中第一个数为拥挤程度，第二个数为方案数。

枚举当前状态$s$，当前点$u$和$s$的子集$t$，现在$t$表示要新加入的子树的状态，则转移式为

$$f[u][s]=\max (f[u][s],(f[u][s\oplus t]\ast g[u][t])+v)$$

其中$\max$表示两个状态取拥挤程度最小的状态，如果拥挤程度相同则将方案数求和。$\ast$表示两个状态合并，即拥挤程度相加、方案数相乘。当$s$为点的全集且$u$只被一条边连接时$v=S$，否则$v=0$，这里的$v$是加在拥挤程度上的。

下面，枚举与$u$相连且不在$s$中的点$v$（这是为能在之后将$v$加入这个连通块），则转移式为

$$g[v][s]=\max (g[v][s],f[u][s]+l\ast c{t}_s+[c{t}_s==1]\ast S)$$

其中$\max$和$+$的意义同上，$l$表示这条边的长度，$c{t}_s$表示$s$的二进制位中$1$的个数（其实就是在算上面的式子$\sum _{i=1}^{n}t{f}_i\times si{z}_i$），后面$[c{t}_s==1]\ast S$表示如果$v$下面只有一个点，也就是有一个只被一条边连接的点，那么拥挤程度要加上$S$。

最后，用每个$f[i][2^n-1]$来更新$ans$（$ans$也是一个结构体，初始值为 { + ∞ , 0 } \{+\infty,0\} {+∞,0}），则$ans$中保存的就是最小的拥挤程度以及能使拥挤程度最小的方案数。

时间复杂度为$O(3^n\cdot n^2)$。

code

#include
using namespace std;
const int N=15,M=15;
const long long inf=1e15;
int n,m,ct[1<<N];
long long S;
struct node{
	int y,w;
};
struct dp{
	long long vl,s;
	friend dp operator+(dp ax,long long bx){
		ax.vl+=bx;
		return ax;
	}
	friend dp operator*(dp ax,dp bx){
		ax.vl+=bx.vl;
		ax.s*=bx.s;
		return ax;
	}
}ans,f[N+5][1<<N],g[N+5][1<<N];
vector<node>G[N+5];
int lb(int i){return i&(-i);}
dp gtmx(dp ax,dp bx){
	if(ax.vl==bx.vl) ax.s+=bx.s;
	if(ax.vl<=bx.vl) return ax;
	return bx;
}
int main()
{
//	freopen("road.in","r",stdin);
//	freopen("road.out","w",stdout);
	scanf("%d%d%lld",&n,&m,&S);
	for(int i=1,x,y,w;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		G[x].push_back((node){y,w});
		G[y].push_back((node){x,w});
	}
	for(int i=1;i<(1<<n);i++) ct[i]=ct[i^lb(i)]+1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<(1<<n);j++){
			f[i][j]=(dp){inf,0};g[i][j]=(dp){inf,0};
		}
		f[i][(1<<i-1)]=(dp){0,1};
	}
	for(int s=1;s<(1<<n);s++){
		for(int u=1;u<=n;u++){
			if(!((s>>u-1)&1)) continue;
			int vs=s^(1<<u-1);
			for(int t=vs;t;t=(t-1)&vs){
				if(t&lb(vs)){
					long long v=(s==(1<<n)-1&&t==vs)*S;
					f[u][s]=gtmx(f[u][s],(f[u][s^t]*g[u][t])+v);
				}
			}
			for(int i=0;i<G[u].size();i++){
				int v=G[u][i].y,w=G[u][i].w;
				if((s>>v-1)&1) continue;
				g[v][s]=gtmx(g[v][s],f[u][s]+w*ct[s]+(ct[s]==1)*S);
			}
		}
	}
	ans=(dp){inf,0};
	for(int i=1;i<=n;i++){
		ans=gtmx(ans,f[i][(1<<n)-1]);
	}
	printf("%lld %lld\n",ans.vl,ans.s);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69