我们不妨设(Park)为(1)号点。将边按边权从小到大排序，考虑选出的边要满足什么条件：
-
选出的边构成原图的一个生成树
-
(1)号点度数不超过(k)
答案就是选边权之和最小的边集，满足上述条件
- 引理1: (M=(S,I))是拟阵，其中(S)为边集，(I)为所有形成生成森林的边集
证明：
遗传性：显然
交换性：假设两个边集(S,T)，其中(|S|<|T|)，且(T)中任意一条边加入(S)都不能形成独立集，那么(T)中每条边的端点一定在(S)中的同一联通块上。对于一个(S)中的联通块(G)的边集(A)，设(T)中满足两端都在(G)中的边集为(B)，由于(T)也是独立集，所以(|B| leq |G|-1 = |A|)。不难归纳出(|T| leq |S|)，与假设矛盾
- 引理2：(M=(S,I))是拟阵，其中(S)为边集，(I)为使得(1)号点度数小于等于(k)的边集
证明：
遗传性：显然
交换性：假设两个边集(S,T)，其中(|S|<|T|)，且(T)中任意一条边加入(S)都不能形成独立集。若(S)中与(1)相连的边数小于(k)，则任意一条不在(S)的边加入都形成独立集，(|T| leq |S|)，与假设矛盾；否则(S)中与(1)相连的边数为(k)，则任意一条不在(S)且不与(1)相连的边加入都形成独立集，设(T)中与(1)相邻的边数为(a,(0 leq a leq k))，则(|T|-a leq |S| -k)，即(|T| leq |S| -k +a leq |S|)，与假设矛盾
那么满足题意的合法边集就是两个拟阵的交，求拟阵交即可，时间复杂度为(O(Tnm^2))
//μ's forever
#include <bits/stdc++.h>
#define M 905
#define ll long long
using namespace std;
int T,n,m,xp[M],yp[M],wp[M],x[M],y[M],w[M],pk,k;
map<string,int> mp;
pair<int,int> ar[M];
int s,t,val[M],fa[M],pre[M];
vector<int> g[M];
bool usd[M],ins[M];
ll dis[M],ans;
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return 0;
fa[x]=y;return 1;
}
bool chk1(bool usd[]){
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i) if(usd[i])
if(!merge(x[i],y[i])) return 0;
return 1;
}
bool chk2(bool usd[]){
int ct=0;
for(int i=1;i<=m;++i)
if(usd[i]&&(x[i]==pk||y[i]==pk))
++ct;
return ct<=k;
}
void spfa(){
for(int i=1;i<=t;++i) dis[i]=1e18;
queue<int> q;dis[s]=0,q.push(s),ins[s]=1;
while(!q.empty()){
int u=q.front();q.pop(),ins[u]=0;
for(int i=0;i<(int)g[u].size();++i){
int v=g[u][i];
if(dis[v]>dis[u]+val[v]){
dis[v]=dis[u]+val[v],pre[v]=u;
if(!ins[v]) ins[v]=1,q.push(v);
}
}
}
}
void matroid_inter(){
memset(usd,0,sizeof(usd));s=m+1,t=m+2;
while(1){
for(int i=1;i<=t;++i) g[i].clear();
for(int i=1;i<=t;++i) if(usd[i]) val[i]=-w[i]; else val[i]=w[i];
for(int i=1;i<=m;++i){ if(!usd[i]) continue;
for(int j=1;j<=m;++j){ if(usd[j]) continue;
usd[i]=0,usd[j]=1;
if(chk1(usd)) g[i].push_back(j);
if(chk2(usd)) g[j].push_back(i);
usd[i]=1,usd[j]=0;
}
}
for(int i=1;i<=m;++i){ if(usd[i]) continue;
usd[i]=1;
if(chk1(usd)) g[s].push_back(i);
if(chk2(usd)) g[i].push_back(t);
usd[i]=0;
}
spfa();
if(dis[t]>1e15) break;
for(int i=pre[t];i!=s;i=pre[i])
usd[i]^=1;
}
}
int main()
{
cin>>T;
while(T--){
mp.clear();ans=n=0;
cin>>m;
for(int i=1;i<=m;++i){
string a,b;
cin>>a>>b>>wp[i];
ar[i]=make_pair(wp[i],i);
if(mp.find(a)!=mp.end()) xp[i]=mp[a];
else{ mp[a]=++n,xp[i]=n; if(a=="Park") pk=n;}
if(mp.find(b)!=mp.end()) yp[i]=mp[b];
else{ mp[b]=++n,yp[i]=n; if(b=="Park") pk=n;}
}
sort(ar+1,ar+1+m);
for(int i=1;i<=m;++i)
x[i]=xp[ar[i].second],y[i]=yp[ar[i].second],w[i]=wp[ar[i].second];
cin>>k;
matroid_inter();
for(int i=1;i<=m;++i) if(usd[i]) ans+=w[i];
cout<<"Total miles driven: "<<ans<<endl;
if(T) puts("");
}
return 0;
}