hdu6664(随机+状压+BFS)

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6664

题意

给定 $n$ 个点,$m$ 条边的无向图,问经过 $k$ 个互不相同的点的路径中权值最大的路径长度

$n\le 10^4,m\le10^4,k\le6$

题解

pxl dalao说这是个经典的随机??好神奇。。

一个比较容易想到也显然很假的算法是做 $k-1$ 次松弛,但是会有重边。。。

如果我们对这 $k$ 个点进行染色,当他们染成不一样的颜色时,我们只要限制不经过相同颜色的点,就可以利用上面的做法了。。

染色时可以随机染色,这样路径出现的概率为 $\frac{k!}{k^k}$ ,所以相应的,我们需要染 $\frac{k^k}{k!}$ 次就可以了。。




代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
*         ┏┓    ┏┓
*         ┏┛┗━━━━━━━┛┗━━━┓
*         ┃       ┃  
*         ┃   ━    ┃
*         ┃ >   < ┃
*         ┃       ┃
*         ┃... ⌒ ...  ┃
*         ┃ ┃
*         ┗━┓ ┏━┛
*          ┃ ┃ Code is far away from bug with the animal protecting          
*          ┃ ┃ 神兽保佑,代码无bug
*          ┃ ┃           
*          ┃ ┃       
*          ┃ ┃
*          ┃ ┃           
*          ┃ ┗━━━┓
*          ┃ ┣┓
*          ┃ ┏┛
*          ┗┓┓┏━━━━━━━━┳┓┏┛
*           ┃┫┫ ┃┫┫
*           ┗┻┛ ┗┻┛
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<time.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 10005
#define nm 64
#define pi 3.1415926535897931
using namespace std;
const ll inf=998244353;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}






struct edge{int t,v;edge*next;}e[NM<<1],*h[NM],*o=e;
void add(int x,int y,int v){o->t=y;o->v=v;o->next=h[x];h[x]=o++;}
int n,m,k,_x,_t,_y,d[NM][nm];
int a[NM],ans,tot;
inline void upd(int&x,int y){x=max(x,y);}

int main(){
srand(time(0));
int _=read();while(_--){
n=read();m=read();k=read();ans=0;
inc(i,1,n)h[i]=0;
o=e;
inc(i,1,m){_x=read();_y=read();_t=read();add(_x,_y,_t);add(_y,_x,_t);}
tot=succ(k)-1;
inc(p,1,200){
inc(i,1,n)a[i]=rand()%k;
inc(i,1,n)inc(j,1,tot)d[i][j]=-inf;
inc(i,1,n)d[i][succ(a[i])]=0;
inc(v,1,tot)inc(i,1,n)if(d[i][v]>=0&&(succ(a[i])&v))
link(i)if((succ(a[j->t])&v)==0)
upd(d[j->t][succ(a[j->t])|v],d[i][v]+j->v);
inc(i,1,n)ans=max(ans,d[i][tot]);
}
if(ans==0)puts("impossible");else printf("%d\n",ans);
}
return 0;
}