两道紫题，哭了
T1 [BZOJ 1977]次小生成树
我们可以使用 (kruskal) 来求出最小生成树，然后通过最小生成树来生成严格次小生成树。
可以证明存在一个严格次小生成树与最小生成树之有一条边的区别，我们枚举非树边加入到树中形成一个奇环树，我们再枚举环上的边断掉一条，我们为了让树边权和尽可能小，我们选择断掉最长的那条边，为了求严格次小生成树，假如最长边与非树边长度相同，则断掉严格次大边。
求环上的边权我们可以使用倍增来维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int read() {
int a = 0, x = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-')
x = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
a = a * 10 + ch - '0';
ch = getchar();
}
return a * x;
}
const int N = 1e5 + 7, M = 1e6 + 7;
const ll inf = 1e18 + 7;
int n, m;
int f[N];
int find(int s) {
if (f[s] == s)
return s;
return f[s] = find(f[s]);
}
int head[N], go[M], nxt[M], val[M], cnt;
void add(int u, int v, int w) {
go[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
val[cnt] = w;
}
int fa[N][31], g[N][31], h[N][31];
void upd(int &a, int &b, int c, int d) {
int ret1 = max(a, c), ret2 = max(b, d);
if (ret1 != a)
ret2 = max(ret2, a);
if (ret1 != c)
ret2 = max(ret2, c);
a = ret1, b = ret2;
}
int dis[N];
void LCA(int a, int b, int &mx1, int &mx2) {
if (dis[a] < dis[b])
swap(a, b);
for (int i = 30; i >= 0; i--) {
if (dis[fa[a][i]] >= dis[b]) {
upd(mx1, mx2, h[a][i], g[a][i]);
a = fa[a][i];
}
}
if (a == b)
return;
for (int i = 30; i >= 0; i--) {
if (fa[a][i] != fa[b][i]) {
upd(mx1, mx2, h[a][i], g[a][i]);
upd(mx1, mx2, h[b][i], g[b][i]);
a = fa[a][i], b = fa[b][i];
}
}
upd(mx1, mx2, h[a][0], g[a][0]);
upd(mx1, mx2, h[b][0], g[b][0]);
}
void dfs(int u) {
for (int i = 1; i <= 30; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
h[u][i] = h[u][i - 1], g[u][i] = g[u][i - 1];
upd(h[u][i], g[u][i], h[fa[u][i - 1]][i - 1], g[fa[u][i - 1]][i - 1]);
}
for (int e = head[u]; e; e = nxt[e]) {
int v = go[e];
if (v == fa[u][0])
continue;
fa[v][0] = u, dis[v] = dis[u] + 1;
h[v][0] = val[e];
dfs(v);
}
}
struct node {
int u, v, w;
friend bool operator<(node a, node b) { return a.w < b.w; }
} arr[M];
ll sum = 0;
bool vis[M];
int main() {
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n = read(), m = read();
for (int i = 1; i <= m; i++) {
arr[i].u = read(), arr[i].v = read(), arr[i].w = read();
}
for (int i = 1; i <= n; i++) f[i] = i;
sort(arr + 1, arr + 1 + m);
for (int i = 1; i <= m; i++) {
if (find(arr[i].u) != find(arr[i].v)) {
sum += arr[i].w;
f[find(arr[i].u)] = find(arr[i].v);
vis[i] = 1;
add(arr[i].u, arr[i].v, arr[i].w);
add(arr[i].v, arr[i].u, arr[i].w);
}
}
dfs(1);
ll ans = inf;
for (int i = 1; i <= m; i++) {
if (vis[i])
continue;
int mx1(0), mx2(0);
LCA(arr[i].u, arr[i].v, mx1, mx2);
if (!mx1)
continue;
// printf("--%d %d--
",mx1,mx2);
if (mx1 != arr[i].w) {
ans = min(ans, (ll)arr[i].w - mx1);
} else if (mx2)
ans = min(ans, (ll)arr[i].w - mx2);
}
printf("%lld", sum + ans);
return 0;
}
T2 [BZOJ 2306][CTSC 2011]幸福路径
正解是倍增Flody求解。 这和LCA什么关系啊？
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define double long double
using namespace std;
int read() {
int a = 0, x = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-')
x = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
a = a * 10 + ch - '0';
ch = getchar();
}
return a * x;
}
const int N = 1e2 + 7, M = 1e6 + 7, inf = 2e9 + 7;
const double eps = 1e-12;
int n, m;
double w[N];
int s;
double p;
double dp[N][N], f[N][N];
int main() {
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n = read(), m = read();
for (int i = 1; i <= n; i++) {
scanf("%Lf", &w[i]);
}
s = read();
scanf("%Lf", &p);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j)
f[i][j] = -inf;
}
}
for (int i = 1; i <= m; i++) {
int a = read(), b = read();
f[a][b] = w[b] * p;
}
double tmp = p;
for (int h = 1; h <= 60; h++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = -inf;
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = max(dp[i][j], f[i][k] + p * f[k][j]);
// printf(" %d %d %d %Lf %Lf %Lf
//%Lf
",i,k,j,dp[i][j],f[i][k],f[k][j],f[i][k]+p*f[k][j]);
}
}
}
p *= p;
// for(int i = 1;i <= n;i ++,putchar('
')) {
// for(int j = 1;j <= n;j ++) {
// printf("dp[%d][%d] = %13.1Lf ",i,j,dp[i][j]);
// }
// }putchar('
');
memcpy(f, dp, sizeof(dp));
if (p < eps)
break;
}
double ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, f[s][i]);
}
printf("%.1Lf", ans + w[s]);
return 0;
}