hdoj题目页面传送门
给定一个无向带权图(g=(v,e),|v|=n,|e|=m),求边权之和最大的有(s)个节点的链的边权之和,即求(maxlimits_{forall iin[1,s],forall jin(i,s],a_ine a_j,forall iin[1,s),(a_i,a_{i+1},l_i)in e}left{sumlimits_{i=1}^{s-1}l_iright})。如果没有符合要求的链,输出(“text{impossible''})。
(nin[2,10^4],min[1,10^4],sin[2,6])。本题多测,最多有(35)组数据,(max(n,m)>100)的最多有(5)组。
先说(bm1)种不是正解的玄学方法
暴搜。。。时间复杂度(mathrm o(mathrm c_n^s)),但很显然非常跑不满,因为这是个稀疏图。而且还可以最优性剪枝优化,假设所有边中最大的边权为(longest),当前的最大答案为(ans),当前还剩(rst)个节点(条边)要搜,目前的边权之和为(now),那么如果(now+rsttimes longestle ans),便可立即停止搜索。这样就可以水过去了。。。
这不是主要内容,时间复杂度到底是多少就不研究了,代码也不贴了。
正解
考虑对一个比原问题弱一点的问题求解:给每个节点(i)染一个([0,s))的颜色(col_i),求边权之和最大的有(s)个节点且这(s)个节点的颜色是([0,1,cdots,s-1])的一个排列的链的边权之和。这个问题很好求,状压dp就可以了。设(dp_{i,j})表示边权之和最大的以(i)为(1)个端点,上面节点颜色互不相同且bitmask为(j)的链的边权之和,边界为(dp_{i,{j}}=begin{cases}0&i=j\-infty&ine jend{cases}),状态转移方程为(dp_{i,j}=begin{cases}maxlimits_{(i,k,l)in e}left{dp_{k,j-col_i}+lright}&col_iin j\-infty&col_inotin jend{cases}),最终答案为(maxlimits_{i=1}^{n}{dp_{i,[1,n]capmathbb z}})。dp顺序要注意,要按照(j)的递增顺序dp,不能按照(i)的顺序(我就在上面wa过)。(简单dp
那么既然这个弱问题这么好求,那我们就强制给每个节点染色。假设我们给每个节点随机染色,那我们来分析一下弱问题的答案就是原问题的正确答案的概率:如果原问题所求得的最长链,在弱问题中,上面所有节点的颜色正好组成([0,1,cdots,s-1])的一个排列,那么弱问题的答案就是原问题的答案,而在所有(s^s)种最长链的颜色序列中,有(s!)种是([0,1,cdots,s-1])的排列,所以概率为(dfrac{s!}{s^s})。当(s=6)时,概率最小为(dfrac{6!}{6^6}approx1.5%)。那么我们只需要在(35)组数据中每组随机染色、求解(300)次,就有(left(1-left(1-dfrac{6!}{6^6}right)^{300}right)^{35}approx71.8%)的概率(很高了)在每组中都至少有一次弱问题的答案是原问题的答案,这样把每次弱问题的答案(max)起来即可。时间也不会炸,时限(15000mathrm{ms})呢。
btw,随机的时候不能写rand()*rand()%s
,这样把两个随机数乘起来,因数会很多,(bmod s)的结果等于(0)的概率就会明显增加,就不均匀了。可以这样写:(rand()*rand()+rand())%s
。
下面贴正解的代码:
#include<bits/stdc++.h> using namespace std; #define int long long//爆int #define pb push_back #define mp make_pair #define x first #define y second const int inf=0x3f3f3f3f3f3f3f3f; int ppc(int x){return __builtin_popcount(x);} int rand0(int r){return (rand()*rand()+rand())%r;}//随机生成[0,r)内的整数 const int n=10000,s=6; int n/*节点数*/,m/*边数*/,s/*要求的链的节点数*/; vector<pair<int,int> > nei[n+1];//邻接表 int col[n+1];//颜色 int ans;//原问题答案 int dp[n+1][1<<s]; void random(){ for(int i=1;i<=n;i++)col[i]=rand0(s);//随机染色 for(int i=1;i<=n;i++)for(int j=1;j<1<<s;j++)dp[i][j]=j==1<<col[i]?0:-inf;//处理边界,顺便初始化 for(int j=1;j<1<<s;j++)for(int i=1;i<=n;i++)if(j&1<<col[i]&&ppc(j)>1/*大小为1的bitmask是边界*/)//枚举状态 for(int k=0;k<nei[i].size();k++){//转移 int x=nei[i][k].x,len=nei[i][k].y; dp[i][j]=max(dp[i][j],dp[x][j^1<<col[i]]+len); } for(int i=1;i<=n;i++)ans=max(ans,dp[i][(1<<s)-1]);//把每次弱问题的答案max起来就有大概率是原问题的答案 } void mian(){ cin>>n>>m>>s; for(int i=1;i<=n;i++)nei[i].clear();//数据不清空,爆零两行泪 while(m--){ int x,y,z; scanf("%lld%lld%lld",&x,&y,&z); nei[x].pb(mp(y,z));nei[y].pb(mp(x,z)); } ans=-inf;//初始化 int randomnum=300;//随机次数 while(randomnum--)random();//随机 if(ans>=0)cout<<ans<<"n"; else puts("impossible"); } signed main(){ srand(19260817);//信仰优化 int testnum;//数据组数 cin>>testnum; while(testnum--)mian(); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602168.html