0x62 最小生成树

走廊泼水节

题意：

给定一棵树，将这棵树加边，扩充为完全图，使完全图的最小生成树为原来的树，询问增加的边权值总和最小是多少

解析：

考虑 kruskal 产生最小生成树的过程：选择当前连接两个连通块边权最小的边。

所以，对于最小生成树上的边，该边一定是两个连通块之间唯一的最短边，设该边权值为 $w$ ，则两个连通块之间的边权值一定大于 $w$ ，最小为 $w + 1$ 。

设树上边连接的两个连通块的大小分别为 $s i z (x), s i z (y)$ 。则两个连通块之间有 $siz(x)\times siz(y)$ 条边，其中有一条是树上的边。对答案的贡献为 $(siz(x)\times siz(y)-1) \times (w+1)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct edge{int u, v, w;edge(){}edge(int u, int v, int w) : u(u), v(v), w(w){}bool operator < (const edge &b) const{return w < b.w;}
}e[maxn];
ll fa[maxn], siz[maxn];
void init(int MAX){for(int i = 1; i <= MAX; i++){fa[i] = i;siz[i] = 1;}
}
int find(int x){return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
void merge(int x, int y){int fx = find(x);int fy = find(y);if(fx != fy){fa[fx] = fy;siz[fy] += siz[fx];}
}
int n;
void solve(){cin >> n;init(n);for(int i = 1, u, v, w; i < n; i++){cin >> u >> v >> w;e[i] = edge(u, v, w);}sort(e+1, e+n);ll ans = 0;for(int i = 1; i < n; i++){int u = e[i].u;int v = e[i].v;int w = e[i].w;int fx = find(u);int fy = find(v);if(fx == fy)continue;ans += (siz[fx]*siz[fy]-1) * (w+1);merge(fx, fy);}cout << ans << endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T;cin >> T;while(T--)solve();return 0;
}

野餐规划

题意：

求图的最小生成树，节点 $1$ 的度最大为 $s$ 。

解析：

首先删去节点 $1$ ，原图变成 $t$ 个连通块 $\ge 1)$ 。

注意到最小生成树的子树也一定是对应子图的最小生成树。所以在每个连通块中求出最小生成树。

然后把 $1$ 节点向每个连通块选最小的边连边，得到一棵生成树，但这棵生成树不一定最小。

对一个连通块而言，可以增加一条 $1$ 号节点连向该连通块的边，然后删去连通块的最小生成树上的一条边，有可能会使权值和更小。

可以求出一个连通块中到 $1$ 号节点的路径上的边权最大值。枚举 $1$ 号节点的边 $(1, p)$ ，如果不在最小生成树上，则可以加边 $(1, p)$ ，删去边 $(u, v)$ ， $(u, v)$ 是节点 $p$ 到节点 $1$ 路径上边权最大的边。

直到节点 $1$ 的度为 $s$ ，或者加边之后边权不会变小。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define mkp(a, b) make_pair((a), (b)) 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e3+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int head[maxn], tot;
struct Edge{int to, nxt, w;
}e[maxm << 1]; 
int g[maxn][maxn];
struct node{int a, b, w;node(){}node(int a, int b, int w) : a(a), b(b), w(w){}bool operator < (const node &rhs) const{return w < rhs.w;} 
}f[maxn]; vector<node> edg;
void add(int a, int b, int c){e[++tot].nxt = head[a];e[tot].to = b;e[tot].w = c;head[a] = tot;
}int fa[maxn];
int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){int fx = find(x);int fy = find(y);if(fx != fy)fa[fx] = fy;
}int cnt; //连通块个数 
int bel[maxn]; // 哪个连通块
vector<int> block[maxn]; 
map<pii, bool> tree;
map<string, int> id;
int n, m, s;
void dfs(int u){bel[u] = cnt;block[cnt].push_back(u);for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(!bel[v] && v != 1)dfs(v);}
}
int kruskal(){sort(edg.begin(), edg.end());int res = 0;for(int i = 0; i < edg.size(); i++){int fx = find(edg[i].a);int fy = find(edg[i].b);if(fx != fy && fx != 1 && fy != 1){res += edg[i].w;fa[fx] = fy;tree[mkp(edg[i].a, edg[i].b)] = 1;tree[mkp(edg[i].b, edg[i].a)] = 1;}}return res;
}void dp(int u, int p){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == p || !tree[mkp(u, v)])continue;if(f[u].w > e[i].w)f[v] = edg[u];elsef[v] = node(u, v, e[i].w);dp(v, u);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> m;id["Park"] = ++n;string a, b;int c;for(int i = 1; i <= m; i++){cin >> a >> b >> c;if(!id.count(a))id[a] = ++n;if(!id.count(b))id[b] = ++n;add(id[a], id[b], c);add(id[b], id[a], c);g[id[a]][id[b]] = g[id[b]][id[a]] = c;edg.push_back(node(id[a], id[b], c));}cin >> s;for(int i = 1; i <= n; i++)fa[i] = i;for(int i = 2; i <= n; i++){if(!bel[i]){++cnt;dfs(i);}} int ans = kruskal();for(int i = 1; i <= cnt; i++){int tmp = INF;int p = -1;for(auto u : block[i]){if(g[1][u] != 0 && tmp > g[1][u]){tmp = g[1][u];p = u;}}ans += tmp;tree[mkp(1, p)] = 1;tree[mkp(p, 1)] = 1;}while(s > cnt){s--;for(int i = 0; i <= n; i++)f[i].w = -1;dp(1, 0);int tmp = -1, p = -1;for(int i = head[1]; i; i = e[i].nxt){int v = e[i].to;if(tmp < f[v].w - e[i].w){tmp = f[v].w - e[i].w;p = v;}}if(tmp == -1)break;ans -= tmp;int u = f[p].a, v = f[p].b;tree[mkp(u, v)] = tree[mkp(v, u)] = false;tree[mkp(1, p)] = tree[mkp(p, 1)] = true;}cout<<"Total miles driven: "<<ans;return 0;
}

沙漠之王

题意：

边有成本和长度两个参数。求图的生成树，使边的总成本与边的总长度的比值最小

解析：

0/1分数规划。

设边的成本为 $a_i$ ，长度为 $b_i$ 。

设最小值的估计值为 $L$ ，判断是否存在一棵生成树，满足 $\sum(a_i-L\times b_i) \le 0$ 。

如果存在一棵生成树，使 $\sum(a_i-L\times b_i) \le 0$ 成立，变形得 $\frac{\sum a_i}{\sum b_i} \le L$ 。则 $L$ 比最小值小
如果对于任意生成树，都有 $\sum(a_i-L\times b_i) > 0$ ，则 $L$ 比最小值大

$L$ 关于解得存在具有单调性。所以可以二分这个 $L$ ，然后判断最小生成树的权值和是否大于零

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e3+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
const double DINF = 1e18;
const double eps = 1e-8; 
typedef pair<int, int> pii;double a[maxn][maxn];
double b[maxn][maxn];
double dis[maxn];
int vis[maxn];
struct point{double x, y, z;
}p[maxn];
double getdis(point i, point j){return (double)sqrt((i.x-j.x)*(i.x-j.x) + (i.y-j.y)*(i.y-j.y));
}
int n; 
int check(double x){memset(vis, 0, sizeof(vis));fill(dis, dis+1+n, DINF);dis[1] = 0;double res = 0;for(int i = 1; i <= n; i++){double tmp = DINF;int po = 1;for(int j = 1; j <= n; j++){if(!vis[j] && tmp > dis[j]){tmp = dis[j];po = j;}}vis[po] = 1;res += dis[po];for(int j = 1; j <= n; j++){if(!vis[j] && dis[j] > fabs(p[po].z-p[j].z) - x*getdis(p[po], p[j]))dis[j] = fabs(p[po].z-p[j].z) - x*getdis(p[po], p[j]);}}return res >= 0.0;
}
void solve(){for(int i = 1; i <= n; i++){cin >> p[i].x >> p[i].y >> p[i].z;}double l = 0, r = 10.0;double ans = 0;while(fabs(r-l) > eps){double mid = (l+r)/2;if(check(mid)){ans = mid;l = mid;}elser = mid;}cout << fixed << setprecision(3) << ans << endl;return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);while(1){cin >> n;if(n == 0)break;solve(); }return 0;
}

黑暗城堡

题意：

求生成树的方案数，使该方案节点 $1$ 与任意节点的距离与原图节点 $1$ 与任意节点的最短距离相等

解析：

询问最短路径树的个数。

Dijkstra 求出单源最短路。然后枚举每一个节点，有多少条边到这个点的路径长度为最短路径。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define int ll
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll mod = (1ll << 31) - 1;
typedef pair<int, int> pii;int head[maxn], tot;
int dis[maxn], vis[maxn];
struct edge{int to, nxt, w;
}e[maxm << 1];
int n, m;
int cnt[maxn];
void add(int a, int b, int c){e[++tot].nxt = head[a];e[tot].to = b;e[tot].w = c;head[a] = tot;
}
void Dijkstra(int st){memset(dis, INF, sizeof(dis));dis[st] = 0;memset(vis, 0, sizeof(vis));for(int i = 1; i < n; i++){int p = -1, d = INF;for(int j = 1; j <= n; j++){if(vis[j])continue;if(dis[j] < d){d = dis[j];p = j;}}vis[p] = 1;for(int j = head[p]; j; j = e[j].nxt){int v = e[j].to;dis[v] = min(dis[v], dis[p] + e[j].w);}}
}
/*
ll prim(int st){memset(vis, 0, sizeof(vis));vis[st] = 1;ll res = 1;for(int i = 1; i < n; i++){int p = -1;int d = INF;for(int j = 2; j <= n; j++){if(vis[j])continue;if(dis[j] < d){d = dis[j];p = j;}}vis[p] = 1;ll cnt = 0;for(int j = head[p]; j; j = e[j].nxt){int v = e[j].to;if(dis[p] == dis[v] + e[j].w)cnt++;}res = res * cnt % mod;}return res;
}*/
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1, u, v, w; i <= m; i++){cin >> u >> v >> w;add(u, v, w);add(v, u, w);		}Dijkstra(1);for(int u = 1; u <= n; u++){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(dis[v] == dis[u] + e[i].w)cnt[v]++;}} ll res = 1;for(int i = 2; i <= n; i++)res = (res * cnt[i]) % mod;	cout << res << endl;return 0;
}