网站公众平台建设方案,湖南seo优化报价,合肥建设网站哪个好,为什么用MyEclipse做网站正题
题目链接:https://www.luogu.com.cn/problem/P3577 题目大意
给出nnn个点mmm条边的一张图#xff0c;每个点有费用CiC_iCi#xff0c;求选出费用和最小的点使得每个点都至少有一个相邻的点#xff08;或自己#xff09;被选择。保证图上不存在超过101010个点的简单…正题
题目链接:https://www.luogu.com.cn/problem/P3577 题目大意
给出nnn个点mmm条边的一张图每个点有费用CiC_iCi求选出费用和最小的点使得每个点都至少有一个相邻的点或自己被选择。保证图上不存在超过101010个点的简单路径。
1≤n≤20000,1≤m≤250001\leq n\leq 20000,1\leq m\leq 250001≤n≤20000,1≤m≤25000 解题思路
突破点肯定在于不超过101010个点的简单路径可以理解为任意一个点为根时的深度都不超过101010因为dfsdfsdfs树上所有边都是返祖边所以考虑状压。
设fi,sf_{i,s}fi,s表示节点iii所在到根节点的链上的节点状态为sss时的最小贡献因为选过的点会影响到下面的节点所以两维的状态不能够转移设0/1/20/1/20/1/2表示这个节点选择了/没有选择且没有覆盖/没有选择且被覆盖。
然后转移挺好写的但是会MLEMLEMLE因为同深度之间的转移相同所以之间设fd,sf_{d,s}fd,s表示深度为ddd的某个点状态为sss即可。
时间复杂度O(310n)O(3^{10}n)O(310n) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e410,S59059;
struct node{int to,next;
}a[N2];
int n,m,tot,cnt,ans,ls[N],q[N];
int dep[N],c[N],f[11][S],pw[11];
bool v[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa){int cnt0;v[x]1;dep[x]dep[fa]1;int ddep[x],MSpw[dep[x]];if(fa){for(int ils[x];i;ia[i].next)if(v[a[i].to])q[cnt]a[i].to;memset(f[d],0x3f,sizeof(f[d]));for(int s0;sMS;s){int No1,Yess;for(int i1;icnt;i){if(s/pw[dep[q[i]]]%30)No2;if(s/pw[dep[q[i]]]%31)Yespw[dep[q[i]]];}f[d][sNo*pw[d]]min(f[d][sNo*pw[d]],f[d-1][s]);f[d][Yes]min(f[d][Yes],f[d-1][s]c[x]);}}else f[0][0]c[x],f[0][1]0,f[0][2]1e9;for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y])continue;dfs(y,x);for(int s0;sMS*3;s)f[d][s]min(f[d1][s],f[d1][s2*pw[d1]]);}return;
}
int main()
{scanf(%d%d,n,m);pw[0]1;for(int i1;i10;i)pw[i]pw[i-1]*3;for(int i1;in;i)scanf(%d,c[i]);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dep[0]-1;for(int i1;in;i)if(!v[i]){dfs(i,0);ansmin(f[0][0],f[0][2]);}printf(%d\n,ans);return 0;
}
