c/c++语言开发共享HDOJ 6664 Andy and Maze

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; }