2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=25, INF=0x3f3f3f3f; int n, mlen, fa[N], b[N], cnt, res, ans, d[N][N]; bool v[N]; struct edge{int x, y, c;} e[2010]; //边的数量开多一点 bool cmp(edge e1, edge e2) {return e1.c<e2.c;} int findfa(int x) {return fa[x]=((fa[x]==x)? fa[x]: findfa(fa[x]));} unordered_map<string, int> mp; void dfs(int sum, int k, int m, int p) { // sum为答案，k为剩下还没连的连通块，m为已经处理的连通块，p为当前可以选的最小位置 if(sum>=res || (cnt-p+1)<k) return ; //答案没有 res优 或 剩下的连通块全部都处理还不能处理完 k个 if(m==cnt) {res=sum; return ;} //都处理完了，更新答案 if(k>0) //还有剩下的 { for(int i=p; i<=cnt; i++) if(v[i]==0) //没有处理的 { v[i]=1; //标记 dfs(sum+d[i][0], k-1, m+1, i+1); //加上和 Park的距离，未处理-1，已处理+1，位置为当前+1 v[i]=0; //回溯 } } else { for(int i=1; i<=cnt; i++) if(v[i]==0) //没有处理的 { int mi=INF; v[i]=1; //寻找已经和 Park联通的点，和第 i个点距离最小 (mi) for(int j=1; j<=cnt; j++) if(v[j]==1) mi=min(mi, d[i][j]); dfs(sum+mi, 0, m+1, 0); //加上最小距离，已经连完，已处理+1，位置为 0(不重要) v[i]=0; //回溯 } } } int main() { scanf("%d", &n); mp.clear(); mlen=0; mp["Park"]=0; //用 map来存边 for(int i=1; i<=n; i++) { string a, b; int c; cin>> a>> b>> c; if(!mp.count(a)) mp[a]=++mlen; if(!mp.count(b)) mp[ b ]=++mlen; e[i]={mp[a], mp[ b ], c}; } int S; scanf("%d", &S); sort(e+1, e+n+1, cmp); cnt=0; memset(b, 0, sizeof(b)); res=ans=0; //res 存和 Park连的边，ans是连通块之间连的边 for(int i=0; i<=21; i++) fa[i]=i; //每个点都是一个连通块 memset(d, 63, sizeof(d)); //d 初始化无穷大 for(int i=1; i<=n; i++) { int x=findfa(e[i].x), y=findfa(e[i].y); if(y==0) swap(x, y); //因为是双向边所以可以把情况都转成 x=0 if(x==y || (x==0 && b[y]!=0)) continue; // x和 y已经联通 if(x==0) {d[++cnt][0]=e[i].c; b[y]=cnt; res+=e[i].c;} //和 Park连边 else if(b[x]!=0 && b[y]!=0) //两个连通块之间连的边 { int t=min(d[b[x]][b[y]], e[i].c); d[b[x]][b[y]]=d[b[y]][b[x]]=t; } else if(b[x]!=0) {ans+=e[i].c; fa[y]=x;} //把 y并进 x else if(b[y]!=0) {ans+=e[i].c; fa[x]=y;} //把 x并进 y else {ans+=e[i].c; fa[y]=x;} //两个点是分散的，先连起来 (将来一定可以连到 Park，因为每个点都有到 Park的路径) } memset(v, 0, sizeof(v)); if(cnt>S) {res=INF; dfs(0, S, 0, 1);} //连通块数量大于 S，那连通块之间先连起来 printf("Total miles driven: %d\n", ans+res); //输出 return 0; }#include<bits/stdc++.h> using namespace std; const int N=5e4+10, M=5e5+10, INF=0x3f3f3f3f; struct edge{int x, y, c;} e[M]; bool cmp(edge e1, edge e2) {return e1.c<e2.c;} int d[N], fa[N], key[N], tmp[N], mlen; int findfa(int x) {return fa[x]=((fa[x]==x)? fa[x]: findfa(fa[x]));} unordered_map<string, int> mp; bool unite(int x, int y, int c) { int tx=findfa(x), ty=findfa(y); if(tx==ty) return 0; if(d[tx]<d[ty]) swap(tx, ty); key[tx]=c; fa[tx]=ty; return 1; } int main() { int n=21, m, S=1, K; scanf("%d", &m); //S代表的是点，K代表的是度数 for(int i=1; i<=n; i++) if(i!=S) fa[i]=i, d[i]=INF; int p=0, tot=0, cnt=0; memset(d, 63, sizeof(d)); mp.clear(); mp["Park"]=1; mlen=1; int ans=0, res=0; for(int i=1; i<=m; i++) { string a, b; int c; cin>> a>> b>> c; if(!mp.count(a)) mp[a]=++mlen; if(!mp.count(b)) mp[ b ]=++mlen; if(mp[a]==S) d[mp[ b ]]=min(d[mp[ b ]], c); else if(mp[ b ]==S) d[mp[a]]=min(d[mp[a]], c); else e[++cnt]={mp[a], mp[ b ], c}; } n=mlen; scanf("%d", &K); sort(e+1, e+cnt+1, cmp); for(int i=1; i<=cnt; i++) if(unite(e[i].x, e[i].y, e[i].c)==1) res+=e[i].c; for(int i=1; i<=n; i++) if(i!=S && findfa(i)==i) p++, res+=d[i], d[i]=INF; for(int i=1; i<=n; i++) if(i!=S && d[i]!=INF) tmp[++tot]=d[i]-key[i]; sort(tmp+1, tmp+tot+1); ans=res; for(int i=1; i<=K-p; i++) res+=tmp[i], ans=min(ans, res); printf("Total miles driven: %d\n", ans); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:56:51
#include<bits/stdc++.h> using namespace std; const int N=25, INF=0x3f3f3f3f; int n, mlen, fa[N], b[N], cnt, res, ans, d[N][N]; bool v[N]; struct edge{int x, y, c;} e[2010]; //边的数量开多一点 bool cmp(edge e1, edge e2) {return e1.c<e2.c;} int findfa(int x) {return fa[x]=((fa[x]==x)? fa[x]: findfa(fa[x]));} unordered_map<string, int> mp; void dfs(int sum, int k, int m, int p) { // sum为答案，k为剩下还没连的连通块，m为已经处理的连通块，p为当前可以选的最小位置 if(sum>=res || (cnt-p+1)<k) return ; //答案没有 res优 或 剩下的连通块全部都处理还不能处理完 k个 if(m==cnt) {res=sum; return ;} //都处理完了，更新答案 if(k>0) //还有剩下的 { for(int i=p; i<=cnt; i++) if(v[i]==0) //没有处理的 { v[i]=1; //标记 dfs(sum+d[i][0], k-1, m+1, i+1); //加上和 Park的距离，未处理-1，已处理+1，位置为当前+1 v[i]=0; //回溯 } } else { for(int i=1; i<=cnt; i++) if(v[i]==0) //没有处理的 { int mi=INF; v[i]=1; //寻找已经和 Park联通的点，和第 i个点距离最小 (mi) for(int j=1; j<=cnt; j++) if(v[j]==1) mi=min(mi, d[i][j]); dfs(sum+mi, 0, m+1, 0); //加上最小距离，已经连完，已处理+1，位置为 0(不重要) v[i]=0; //回溯 } } } int main() { scanf("%d", &n); mp.clear(); mlen=0; mp["Park"]=0; //用 map来存边 for(int i=1; i<=n; i++) { string a, b; int c; cin>> a>> b>> c; if(!mp.count(a)) mp[a]=++mlen; if(!mp.count(b)) mp[ b ]=++mlen; e[i]={mp[a], mp[ b ], c}; } int S; scanf("%d", &S); sort(e+1, e+n+1, cmp); cnt=0; memset(b, 0, sizeof(b)); res=ans=0; //res 存和 Park连的边，ans是连通块之间连的边 for(int i=0; i<=21; i++) fa[i]=i; //每个点都是一个连通块 memset(d, 63, sizeof(d)); //d 初始化无穷大 for(int i=1; i<=n; i++) { int x=findfa(e[i].x), y=findfa(e[i].y); if(y==0) swap(x, y); //因为是双向边所以可以把情况都转成 x=0 if(x==y || (x==0 && b[y]!=0)) continue; // x和 y已经联通 if(x==0) {d[++cnt][0]=e[i].c; b[y]=cnt; res+=e[i].c;} //和 Park连边 else if(b[x]!=0 && b[y]!=0) //两个连通块之间连的边 { int t=min(d[b[x]][b[y]], e[i].c); d[b[x]][b[y]]=d[b[y]][b[x]]=t; } else if(b[x]!=0) {ans+=e[i].c; fa[y]=x;} //把 y并进 x else if(b[y]!=0) {ans+=e[i].c; fa[x]=y;} //把 x并进 y else {ans+=e[i].c; fa[y]=x;} //两个点是分散的，先连起来 (将来一定可以连到 Park，因为每个点都有到 Park的路径) } memset(v, 0, sizeof(v)); if(cnt>S) {res=INF; dfs(0, S, 0, 1);} //连通块数量大于 S，那连通块之间先连起来 printf("Total miles driven: %d\n", ans+res); //输出 return 0; }
兼容出发点不是1的版本：#include<bits/stdc++.h> using namespace std; const int N=5e4+10, M=5e5+10, INF=0x3f3f3f3f; struct edge{int x, y, c;} e[M]; bool cmp(edge e1, edge e2) {return e1.c<e2.c;} int d[N], fa[N], key[N], tmp[N], mlen; int findfa(int x) {return fa[x]=((fa[x]==x)? fa[x]: findfa(fa[x]));} unordered_map<string, int> mp; bool unite(int x, int y, int c) { int tx=findfa(x), ty=findfa(y); if(tx==ty) return 0; if(d[tx]<d[ty]) swap(tx, ty); key[tx]=c; fa[tx]=ty; return 1; } int main() { int n=21, m, S=1, K; scanf("%d", &m); //S代表的是点，K代表的是度数 for(int i=1; i<=n; i++) if(i!=S) fa[i]=i, d[i]=INF; int p=0, tot=0, cnt=0; memset(d, 63, sizeof(d)); mp.clear(); mp["Park"]=1; mlen=1; int ans=0, res=0; for(int i=1; i<=m; i++) { string a, b; int c; cin>> a>> b>> c; if(!mp.count(a)) mp[a]=++mlen; if(!mp.count(b)) mp[ b ]=++mlen; if(mp[a]==S) d[mp[ b ]]=min(d[mp[ b ]], c); else if(mp[ b ]==S) d[mp[a]]=min(d[mp[a]], c); else e[++cnt]={mp[a], mp[ b ], c}; } n=mlen; scanf("%d", &K); sort(e+1, e+cnt+1, cmp);for(int i=1; i<=cnt; i++) if(unite(e[i].x, e[i].y, e[i].c)==1) res+=e[i].c; for(int i=1; i<=n; i++) if(i!=S && findfa(i)==i) p++, res+=d[i], d[i]=INF; for(int i=1; i<=n; i++) if(i!=S && d[i]!=INF) tmp[++tot]=d[i]-key[i]; sort(tmp+1, tmp+tot+1); ans=res; for(int i=1; i<=K-p; i++) res+=tmp[i], ans=min(ans, res); printf("Total miles driven: %d\n", ans); return 0;}
</p>
- 1
