random
给出一个有向无环的连通图。小 A 需要从 \(1\) 号点走到 \(n\) 号点。保证图里所有的点都能够到达 \(N\) 号点。小 A 每次会等概率的随机一个能直接走到的节点走过去。求小 A 从一号点走到 \(n\) 号点期望需要经过多长的路径。
对于 \(30\%\) 的数据，保证 \(1 \le n, m \le 15\)。
对于 \(100\%\) 的数据，保证 \(1 \le n, m \le 2 \times 10^5\)。
边权不会超过 \(10000\) 且为正整数。
30 pts 做法
枚举从 \(1\) 到 \(n\) 的所有路径计算。
100 pts 做法
经典期望题。考虑建反图，记 \(f_i\) 为 从 \(i\) 走到 \(n\) 点的期望路径长。
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
ll n, m, d[N], d1[N];
vector < pair < int, int > > G[N];
double f[N];
int main(){
freopen("random.in", "r", stdin);
freopen("random.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= m; i++){
int u = read(), v = read(), w = read();
d[u]++; d1[u]++; G[v].push_back(make_pair(u, w));
}
queue < int > q;
q.push(n);
while(!q.empty()){
int u = q.front(); q.pop();
for(auto p : G[u]){
int v = p.first, w = p.second;
f[v] += (1.0 / d[v]) * (f[u] + w);
if(--d1[v] == 0) q.push(v);
}
}
printf("%.2lf\n", f[1]);
return 0;
}
path
给定一个 \(N\) 个点 \(M\) 条边的有向图，可能包含自环或重边，不保证连通性。
每个点上有一个小写英文字母。对于一条路径，我们认为这条路径的权值是其中出现次数最多的字母的出现次数。现在小 A 希望你能够告诉他，这个图中的最大路径权值是多少。特殊的，如果这个权值是 \(\text{inf}\)，则输出 \(0\) 即可。
对于 \(20\%\) 的数据，保证 \(1 \le n \le 15\)。
对于 \(50\%\) 的数据，保证 \(1 \le n \le 10^3\)。
对于 \(80\%\) 的数据，保证 \(1 \le n \le 10^5\)。
对于 $100% 的数据，保证 \(1 \le n, m \le 5 \times 10^5\)。
100 pts 做法
显然当图上有环时答案为 \(\text{inf}\)。下面考虑有向无环情形。
#include<bits/stdc++.h>
#define ll long long
#define N 500005
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
ll n, m, val[N], d[N], cnt;
ll f[N][30], ans;
vector < int > G[N];
int main(){
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
n = read(), m = read();
string s; cin >> s;
for(int i = 0; i < n; i++)
val[i + 1] = s[i] - 'a' + 1;
for(int i = 1; i <= m; i++){
int u = read(), v = read();
G[u].push_back(v); d[v]++;
}
queue < int > q;
for(int i = 1; i <= n; i++) if(!d[i]) q.push(i);
while(!q.empty()){
int u = q.front(); q.pop(); cnt++;
for(auto v : G[u]){
if(!(--d[v])) q.push(v);
for(int i = 1; i <= 26; i++){
if(i == val[u]) f[v][i] = max(f[v][i], f[u][i] + 1);
else f[v][i] = max(f[v][i], f[u][i]);
}
}
}
if(cnt != n) { printf("0\n"); return 0; }
for(int i = 1; i <= n; i++) f[i][val[i]]++;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= 26; j++)
ans = max(ans, f[i][j]);
printf("%lld\n", ans);
return 0;
}