2021 1|2
10064. 「一本通 3.1 例 1」黑暗城堡
mind
这个题显然是求最短路径树的个数
最短路径树:对于根节点u，它到任意v的最小距离等于树上的距离
考虑(dijkstra)，每次选择一个与起始节点最小的点加入集合，所以选择的边组成的集合就是一种最短路径树，至于统计方案，我们可以判断每一条边，如果(dis[v]=dis[u]+e[i])方案数可以累乘，不过如果更新(dijkstra)需要重置到这一点的最短路方案数。当然我们也可以在跑完(dijkstra)后统计答案。
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
const int M = 5e5;
const int inf = 0x3f3f3f;
int n,m,mod,js,head[1005];
struct edge{
int u,v,w,nxt;
}e[M << 1];
void add_edge(int u,int v,int w){
e[++js].v = v;
e[js].w = w;
e[js].nxt = head[u];
head[u] = js;
}
struct node{
int u,w;
bool operator < (const node a)const{
return w > a.w;
}
};
bool vis[1005];
int dis[1005],ans[1005];
priority_queue<node> q;
void dij(int s){
memset(dis, inf,sizeof(dis));
q.push((node){s,0});
dis[s] = 0;ans[1] = 1;
while(!q.empty()){
node tp = q.top();q.pop();
int u = tp.u;
if(vis[u])continue;
vis[u] = 1;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(dis[v] > dis[u] + e[i].w){
ans[v] = 1;dis[v] = dis[u] + e[i].w;
q.push((node){v,dis[v]});
}
else if(dis[v] == dis[u] + e[i].w)
ans[v]++;
}
}
return;
}
signed main(){
std::ios::sync_with_stdio(false);
mod = pow(2,31) - 1;
cin>>n>>m;
for(int i = 1,u,v,w;i <= m; i++){
cin>>u>>v>>w;
add_edge(u, v, w);
add_edge(v, u, w);
}
dij(1);
int Ans = 1;
for(int i = 1;i <= n; i++){
Ans *= ans[i]%mod;
Ans %= mod;
}
cout<<Ans%mod;
}
一本通 3.1 例 2」北极通讯网络
mind
逆向思维，把所有可以相互连通的村庄连接起来，构成一个图，卫星台数就是图中连通支的个数。
问题转化为：找到一个最小的(d)，使得把所有权值大于(d)的边去掉之后，连通支的个数(<=k)
定理1
如果去掉所有权值大于d的边后，最小生成树被分割成为(k)个连通支，则图也被分割成为(k)个连通支
证明用反证法
所以该题的解就是生成树中第k长的边
注意定义类型，把ans数组定义成了int类型调了半个小时
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int M = 510;
const int N = 1e6 + 4;
int n,k,fa[M],cnt,js;
double ans[M];
struct Pots{
int x,y;
}p[N << 1];
struct node{
int xx,yy;
double dis;
}a[N<<1];
double calc(int x_1,int x_2,int y_1,int y_2){
return sqrt((x_1 - x_2)*(x_1 - x_2) + (y_1 - y_2)*(y_1 - y_2));
}
int find(int x){
if (fa[x] != x)fa[x] = find(fa[x]);
return fa[x];
}
bool cmp(node a,node b){
return a.dis < b.dis;
}
int main(){
cin>>k>>n;
if(k > n){
printf("0.00");
return 0;
}
for(int i = 1;i <= n; i++) cin>>p[i].x>>p[i].y;
for(int i = 1;i <= n; i++) fa[i] = i;
for(int i = 1;i <= n; i++)
for(int j = i + 1;j <= n; j++){
a[++cnt] = (node){i,j,calc(p[i].x,p[j].x,p[i].y,p[j].y)};
}
sort(a + 1,a + cnt + 1,cmp);
for(int i = 1; i <= cnt; i++){//构造最小生成树
int x = find(a[i].xx),y = find(a[i].yy);
if(x != y){
fa[x] = y;
ans[++js] = a[i].dis;
}
}
printf("%.2lf",ans[js - k + 1]);
}
10066. 「一本通 3.1 练习 1」新的开始
mind
最小生成树
由于每个矿井建修电站都有费用（可看作有权值的点），贪心优先选择权值最小的点，然后构建最小生成树，若两者连线消耗比要连接的点的权值小，更新这个要连的点的权值，同时ans记录答案
由于数据很水，所以用链接矩阵存图
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int M = 1e5;
const int inf = 0x3f3f3f3f;
int n,di[301],vis[301],minn,k,ans;
int js,head[301],e[301][301];
int main(){
std::ios::sync_with_stdio(false);
cin>>n;
for(int i = 1;i <= n; i++)cin>>di[i];
for(int i = 1;i <= n; i++)
for(int j = 1,w;j <= n;j++){
cin >>w;
e[i][j] = w;
}
for(int i = 1;i <= n; i++){
minn = inf;
for(int j = 1;j <= n; j++)
if(!vis[j] && minn > di[j])
minn = di[j],k = j;
vis[k] = 1;ans += minn;
for(int j = 1;j <= n; j++){
if(!vis[j] && di[j] > e[j][k])
di[j] = e[j][k];
}
}
printf("%d",ans);
}
10067. 「一本通 3.1 练习 2」构造完全图
mind
完全图：有(n)个点，(frac{n*(n-1)}{2})条边构成的图
要求仅有一条最小生成树，所以加边的时候一定比当前边要小
(prim):把所有的点分为两个集合，(A),(B),起初(A)集合中只有一个点，然后从(B)每拿一个点就要添加
(cnt[x] * cnt[y] - 1)条边（x , y分别为两点的父亲节点（并查集）），所加的边至少要比当前的边大1.否则不满足仅有一个最小生成树的条件（模一下过程就好了）
/*
work by:Ariel_
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int M = 1e5 + 2;
int n,fa[M],ans,cnt[M];
struct edge{
int u,v,w;
}e[M];
int find(int x){
if(fa[x]!=x)return fa[x]=find(fa[x]);
else return fa[x];
}
bool cmp(edge a,edge b){return a.w<b.w;}
signed main(){
std::ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <=n - 1; i++){
cin>>e[i].u>>e[i].v>>e[i].w;
ans += e[i].w;
}
for(int i = 1;i <= n; i++){
fa[i] = i;cnt[i] = 1;
}
sort(e + 1,e + n,cmp);
for(int i = 1; i < n; i++){
int x = find(e[i].u),y = find(e[i].v);
if(x != y){
ans += (cnt[x]*cnt[y] - 1)*(e[i].w + 1);
fa[y] = x;
cnt[x] += cnt[y];
}
}
printf("%lld",ans);
}