链接
https://ac.nowcoder.com/acm/contest/9700/E
题意
给定一张 $n$ 个点 $m$ 条边的无向带边权连通图，点有颜色，为黑或白，保证无自环和重边。
定义一次操作为：随机选择两个不同的点，将它们之间的最短路上的点全部染黑（若有多条最短路就都染黑）。
现在你想知道，经过 $k$ 次操作后，黑色点的期望个数是多少。
思路
用 Floyd 求出每个点在多少条最短路中。
根据期望的线性性质对每个点的期望求和。
若这个点本来就是黑色的，则直接加 $1$。
否则容斥后就转化成求该点经过 $k$ 次后不被染黑的概率，用 $1$ 减就是该点贡献。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL MOD=1023694381;
const int N=505;
int n,m,k,a[N],cnt[N];
LL dist[N][N];
void floyd() {
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(dist[i][j]==dist[i][k]+dist[k][j])
++cnt[k];
}
LL qpow(LL a,LL b) {
LL ret=1;
while(b) {
if(b&1) ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
memset(dist,0x3f,sizeof dist);
for(int i=1;i<=n;i++) dist[i][i]=0;
for(int i=1;i<=m;i++) {
int u,v,w;
cin>>u>>v>>w;
dist[u][v]=dist[v][u]=w;
}
floyd();
LL res=0;
LL C2=qpow(n*(n-1)/2,MOD-2);
for(int i=1;i<=n;i++) {
if(a[i]==1) ++res;
else res=(res+(1+MOD-qpow((1+MOD-cnt[i]*C2%MOD)%MOD,k))%MOD)%MOD;
}
cout<<res<<'\n';
return 0;
}
|