正题
题目链接:https://www.luogu.com.cn/problem/P3959
题目大意
n
n
n个点，
m
m
m条边，求一棵有根生成树权值最小。对于一条边
(
f
a
,
x
,
w
)
(fa,x,w)
(fa,x,w)会产生权值
d
e
p
f
a
∗
w
dep_{fa}*w
depfa∗w。
解题思路
我们模拟退火每次随机一个序列，然后贪心一个一个加入生成树中。然后一系列玄学参数即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
using namespace std
;
const ll N
=13,inf
=5e6+10;
const double delit
=0.996;
ll n
,m
,a
[N
][N
],p
[N
],k
[N
],v
[N
],ans
=inf
;
ll
calc(){
memset(v
,0,sizeof(v
));
ll ans
=0;v
[p
[1]]=1;k
[p
[1]]=0;
for(ll i
=2;i
<=n
;i
++){
ll k
=1e18;
for(ll j
=1;j
<i
;j
++){
ll x
=p
[i
],y
=p
[j
];
if(a
[y
][x
]<inf
&&a
[y
][x
]*v
[y
]<k
)
k
=a
[y
][x
]*v
[y
],v
[x
]=v
[y
]+1;
}
ans
+=k
;
}
return ans
;
}
void S_A(){
double t
=10000;
srand(rand());
while(t
>1e-15){
ll x
=rand()%n
+1,y
=rand()%n
+1;
swap(p
[x
],p
[y
]);
ll now
=calc(),k
=now
-ans
;
if(k
<0)ans
=now
;
else if(exp(-1.0*k
/t
)*RAND_MAX
<rand())swap(p
[x
],p
[y
]);
t
*=delit
;
}
return;
}
void Solve(){
for(ll i
=1;i
<=n
;i
++)p
[i
]=i
;
ans
=calc();
for(ll i
=1;i
<=100;i
++)S_A();
return;
}
int main()
{
srand(19260817+114514);
scanf("%lld%lld",&n
,&m
);
memset(a
,0x3f,sizeof(a
));
for(ll i
=1;i
<=m
;i
++){
ll x
,y
,w
;
scanf("%lld%lld%lld",&x
,&y
,&w
);
a
[x
][y
]=a
[y
][x
]=min(a
[x
][y
],w
);
}
Solve();
printf("%lld\n",ans
);
}
