HDOJ 6664 Andy and Maze

hdoj题目页面传送门

给定一个无向带权图\(g=(v,e),|v|=n,|e|=m\)，求边权之和最大的有\(s\)个节点的链的边权之和，即求\(\max\limits_{\forall i\in[1,s],\forall j\in(i,s],a_i\ne a_j,\forall i\in[1,s),(a_i,a_{i+1},l_i)\in e}\left\{\sum\limits_{i=1}^{s-1}l_i\right\}\)。如果没有符合要求的链，输出\(``\text{impossible''}\)。

\(n\in[2,10^4],m\in[1,10^4],s\in[2,6]\)。本题多测，最多有\(35\)组数据，\(\max(n,m)>100\)的最多有\(5\)组。

先说\(\bm1\)种不是正解的玄学方法

暴搜。。。时间复杂度\(\mathrm o(\mathrm c_n^s)\)，但很显然非常跑不满，因为这是个稀疏图。而且还可以最优性剪枝优化，假设所有边中最大的边权为\(longest\)，当前的最大答案为\(ans\)，当前还剩\(rst\)个节点（条边）要搜，目前的边权之和为\(now\)，那么如果\(now+rst\times longest\le 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&i\ne j\end{cases}\)，状态转移方程为\(dp_{i,j}=\begin{cases}\max\limits_{(i,k,l)\in e}\left\{dp_{k,j-col_i}+l\right\}&col_i\in j\\-\infty&col_i\notin j\end{cases}\)，最终答案为\(\max\limits_{i=1}^{n}\{dp_{i,[1,n]\cap\mathbb 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\)起来即可。时间也不会炸，时限\(15000\mathrm{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;
}