本文主要是介绍2023NOIP A层联测14 修路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意
有一个有 n n n个点 m m m条边的无向连通图,第 i i i条边连接点 u i u_i ui和 v i v_i vi,长度为 l i l_i li。
你想要求这个图的一棵生成树,并规定一个中心点 m i d mid mid。定义一种规划的拥挤指数为 k × S + ∑ i = 1 n d i s ( i , m i d ) k\times S+\sum\limits_{i=1}^ndis(i,mid) k×S+i=1∑ndis(i,mid),其中有 k k k表示只被一条边连接的点的数量, d i s ( u , v ) dis(u,v) dis(u,v)表示点 u u u到点 v v v的距离, S S S为给定的常数。
求如何修建道路和规划中心点,才能使拥挤程度最小,以及有多少种方案(求生成树+规划中心点)能使拥挤程度最小。
1 ≤ n ≤ 15 , n − 1 ≤ m ≤ n ( n − 1 ) 2 , 0 ≤ l i , S ≤ 1 0 9 1\leq n\leq 15,n-1\leq m\leq \frac{n(n-1)}{2},0\leq l_i,S\leq 10^9 1≤n≤15,n−1≤m≤2n(n−1),0≤li,S≤109
时间限制 7000 m s 7000ms 7000ms,空间限制 1024 M B 1024MB 1024MB。
题解
我们枚举每个点,让它作为中心点,并找到一个拥挤程度最小的生成树。
我们发现 ∑ i = 1 n d i s ( i , m i d ) \sum\limits_{i=1}^ndis(i,mid) i=1∑ndis(i,mid)其实等于 ∑ i = 1 n t f i × s i z i \sum\limits_{i=1}^ntf_i\times siz_i i=1∑ntfi×sizi,其中 l e n i len_i leni表示当 m i d mid mid为根时点 i i i到父亲的距离, s i z i siz_i sizi表示子树 i i i的大小。
因为 n n n比较小,我们可以使用状压 D P DP DP。
设 f [ i ] [ s ] f[i][s] f[i][s]表示当前的根节点为 i i i, i i i的子树中点的集合为 s s s时的拥挤程度和方案数(要保存两个数,可以用结构体), g [ i ] [ s ] g[i][s] g[i][s]表示当前根节点为 i i i且根节点只有一个儿子, i i i的子树中(不包括 i i i)的点的集合为 s s s时的拥挤程度和方案数(其实就是一个连通块连出一条边到点 i i i)。注意虽然根节点有可能只被一条边连接,但当 s s s不为点的全集时,这里的 i i i都不算入 k k k中。
初始值为 f [ i ] [ 2 i − 1 ] = { 0 , 1 } f[i][2^{i-1}]=\{0,1\} f[i][2i−1]={0,1},其余的 f f f值和 g g g值为 { + ∞ , 0 } \{+\infty,0\} {+∞,0}。其中第一个数为拥挤程度,第二个数为方案数。
枚举当前状态 s s s,当前点 u u u和 s s s的子集 t t t,现在 t t t表示要新加入的子树的状态,则转移式为
f [ u ] [ s ] = max ( f [ u ] [ s ] , ( f [ u ] [ s ⊕ t ] ∗ g [ u ] [ t ] ) + v ) f[u][s]=\max(f[u][s],(f[u][s\oplus t]*g[u][t])+v) f[u][s]=max(f[u][s],(f[u][s⊕t]∗g[u][t])+v)
其中 max \max max表示两个状态取拥挤程度最小的状态,如果拥挤程度相同则将方案数求和。 ∗ * ∗表示两个状态合并,即拥挤程度相加、方案数相乘。当 s s s为点的全集且 u u u只被一条边连接时 v = S v=S v=S,否则 v = 0 v=0 v=0,这里的 v v v是加在拥挤程度上的。
下面,枚举与 u u u相连且不在 s s s中的点 v v v(这是为能在之后将 v v v加入这个连通块),则转移式为
g [ v ] [ s ] = max ( g [ v ] [ s ] , f [ u ] [ s ] + l ∗ c t s + [ c t s = = 1 ] ∗ S ) g[v][s]=\max(g[v][s],f[u][s]+l*ct_s+[ct_s==1]*S) g[v][s]=max(g[v][s],f[u][s]+l∗cts+[cts==1]∗S)
其中 max \max max和 + + +的意义同上, l l l表示这条边的长度, c t s ct_s cts表示 s s s的二进制位中 1 1 1的个数(其实就是在算上面的式子 ∑ i = 1 n t f i × s i z i \sum\limits_{i=1}^ntf_i\times siz_i i=1∑ntfi×sizi),后面 [ c t s = = 1 ] ∗ S [ct_s==1]*S [cts==1]∗S表示如果 v v v下面只有一个点,也就是有一个只被一条边连接的点,那么拥挤程度要加上 S S S。
最后,用每个 f [ i ] [ 2 n − 1 ] f[i][2^n-1] f[i][2n−1]来更新 a n s ans ans( a n s ans ans也是一个结构体,初始值为 { + ∞ , 0 } \{+\infty,0\} {+∞,0}),则 a n s ans ans中保存的就是最小的拥挤程度以及能使拥挤程度最小的方案数。
时间复杂度为 O ( 3 n ⋅ n 2 ) O(3^n\cdot n^2) O(3n⋅n2)。
code
#include<bits/stdc++.h>
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;
}
这篇关于2023NOIP A层联测14 修路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!