C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2020-08-22 16:06:31

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int N=505;
struct E {
	int u,v,w;
	E() {}
	E(int u,int v,int w):u(u),v(v),w(w) {}
	bool operator < (const E &a) const {
		return w<a.w;
	}
}mn[N],mx[N];
int n,m,k,dist[N][N],fa[N],id[N],vis[N];
bool st[N][N];
vector<E> e;
map<string,int> mp;
int find(int x) {
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int kruskal() {
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e.begin(),e.end());
	int res=0;
	for(int i=0;i<e.size();i++)
		if(id[e[i].u]==id[e[i].v]) {
			int tx=find(e[i].u),ty=find(e[i].v);
			if(tx==ty) continue;
			fa[tx]=ty;
			res+=e[i].w;
			st[e[i].u][e[i].v]=st[e[i].v][e[i].u]=true;
		}
	return res;
}
void dfs1(int u,int t) {
	id[u]=t;
	for(int i=2;i<=n;i++) if(dist[u][i]&&!id[i]) dfs1(i,t);
}
void dp(int u,int fa) {
	for(int i=2;i<=n;i++) {
		if(i==fa||!st[u][i]) continue;
		if(u!=1) {
			if(mx[u].w>dist[u][i]) mx[i]=mx[u];
			else mx[i]=E(u,i,dist[u][i]);
		}
		dp(i,u);
	}
}
int solve() {
	int t=0;
	for(int i=2;i<=n;i++) if(!id[i]) dfs1(i,++t);
	int res=kruskal();
	for(int i=1;i<=t;i++) mn[i].w=0x3f3f3f3f;
	for(int i=2;i<=n;i++) if(dist[1][i]&&dist[1][i]<mn[id[i]].w) mn[id[i]]=E(1,i,dist[1][i]);
	for(int i=2;i<=n;i++) {
		if(vis[id[i]]) continue;
		st[1][mn[id[i]].v]=st[mn[id[i]].v][1]=true;
		res+=mn[id[i]].w;
		vis[id[i]]=true;
		k--;
	}
	while(k) {
		mx[1].w=0xc0c0c0c0;
		for(int i=2;i<=n;i++) {
			if(st[1][i]) mx[i].w=0xc0c0c0c0;
			else mx[i].w=0;
		}
		dp(1,0);
		int temp=1;
		for(int i=2;i<=n;i++) {
			if(st[1][i]||!dist[1][i]) continue;
			if(dist[1][i]-mx[i].w<dist[1][temp]-mx[temp].w) temp=i;
		}
		st[1][temp]=st[temp][1]=true;
		st[mx[temp].u][mx[temp].v]=st[mx[temp].v][mx[temp].u]=false;
		if(dist[1][temp]-mx[temp].w>0) break;
		res+=dist[1][temp]-mx[temp].w;
		k--;
	}
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	mp["Park"]=++n;
    cin>>m;
    for(int i=1;i<=m;i++) {
    	string a,b;
    	int w;
    	cin>>a>>b>>w;
    	if(!mp.count(a)) mp[a]=++n;
    	if(!mp.count(b)) mp[b]=++n;
    	dist[mp[a]][mp[b]]=dist[mp[b]][mp[a]]=w;
    	e.push_back(E(mp[a],mp[b],w));
    }
    cin>>k;
    cout<<"Total miles driven: "<<solve()<<'\n';
    return 0;
}

C++ 解法, 执行用时: 363ms, 内存消耗: 456K, 提交时间: 2022-02-09 10:20:49

#include<bits/stdc++.h>
using namespace std;
int n,k,num,cnt,fa[22],ans,bns,ss[22][22],a,b,c,t;
map<string,int>mm;
struct fy{int from,to,d;bool operator<(const fy&a)const{return d<a.d;};}q[430];
char str[30],str1[30];
void add(int a,int b,int c){q[++num]=(fy){a,b,c};}
int can(int a){
	bns=0;
	int he=0,w=1;
	while(a){
		w++;
		if(a&1){he++;fa[w]=1;if(ss[1][w]==ss[0][0])return 0;bns+=ss[1][w];}
		a>>=1;
	}
	if(he<=k)return he;
	return 0;
}
int find(int a){while(a-fa[a])a=fa[a]=fa[fa[a]];return a;}
void ku(int x){
	if(!x)return;
	for(int i=1;i<=num;i++){
		if(q[i].from==1||q[i].to==1)continue;
		int a=find(q[i].from),b=find(q[i].to);
		if(a-b){if(x==(cnt-1))break;fa[a]=b;x++;bns+=q[i].d;if(bns>ans)return;}
	}
	if(x==(cnt-1))ans=min(ans,bns);
}
int main(){
    mm.clear();
    cnt=0;num=0;
    cin>>n;
    memset(ss,0x3f,sizeof ss);
    mm["Park"]=++cnt;ans=ss[0][0];
    for(int i=1;i<=n;i++){
        cin>>str>>str1>>c;
        if(!mm[str])mm[str]=++cnt;
        if(!mm[str1])mm[str1]=++cnt;
        a=mm[str];b=mm[str1];
        ss[a][b]=min(ss[a][b],c);
        ss[b][a]=ss[a][b];
    }
    cin>>k;
    for(int i=1;i<=cnt;i++)for(int j=i+1;j<=cnt;j++)if(ss[i][j]&&(ss[i][j]!=ss[0][0]))add(i,j,ss[i][j]);
    sort(q+1,q+1+num);
    for(int s=0;s<(1<<(cnt-1));s++){for(int i=1;i<=cnt;i++)fa[i]=i;ku(can(s));}
    cout<<"Total miles driven: "<<ans<<"\n";
	return 0;
}