好难写的一个题.
等价题意:求一个最小生成树,满足点1的度数不超过给定的$k$.
先不考虑1,求出其它所有点所构成的最小生成树森林(设有$T$棵树)
让每一棵最小生成树都选出一条边权最小的边,与1连接.
所以若$T>k$,则无解.
这样我们就得到了一种可行解,1的度数为$T$.
接下来我们尝试让答案更优:
对于所有与1相连,且未被使用过的边$(1,v,w)$,计算出原本的最小生成树上1到$v$的最大边$(u’,v’,maxw)$,找出最大的$w-maxw$.
- 若$w-maxw\le 0$,修改不会使答案更优,结束
- 否则将这条边改成$(1,v,w)$,答案减小了$w-maxw$
重复上述步骤,直至1的度数为$k$或答案不会更优而结束(实际实现的时候,不用每次都去找最大边,可以先dfs一遍求出到所有点的最大边,再逐个尝试)
实现细节很多,贴一下实现.时间复杂度$O(k\times (n+m))$
/**********///省略快读
#define MAXN 51
struct Union_Find_Set
{
ll fa[MAXN];
void build(ll n)
{
for(ll i=1;i<=n;++i)fa[i]=i;
}
ll find(ll x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
bool uni(ll x,ll y)
{
x=find(x),y=find(y);
if(x==y)return 0;
fa[x]=y;
return 1;
}
}s;
struct Edge
{
ll u,v,w;
bool operator <(const Edge& t)
const
{
return w<t.w;
}
Edge(ll _u=0,ll _v=0,ll _w=0)
{
u=_u,v=_v,w=_w;
}
}maxe[MAXN];
std::vector<Edge>e;
ll g[MAXN][MAXN],used[MAXN][MAXN],out[MAXN],dis[MAXN],n,m;
std::map<str,ll>p;
str a,b;
ll ans=0;
void dfs(ll u)
{
for(ll i=2;i<=n;++i)
if(maxe[i].v==0&&g[u][i]&&used[u][i])
{
if(maxe[u].w>g[u][i])maxe[i]=maxe[u];
else
{
maxe[i]=Edge(u,i,g[u][i]);
}
dfs(i);
}
}
void Kru()
{
s.build(n);
for(std::vector<Edge>::iterator it=e.begin();it!=e.end();++it)
if(it->u!=1&&it->v!=1&&s.uni(it->u,it->v))
{
used[it->u][it->v]=used[it->v][it->u]=1;
ans+=it->w;
}
}
int main()
{
memset(g,0x3f,sizeof g);memset(dis,0x3f,sizeof dis);
n=1;p["Park"]=1;
m=read();
for(ll i=1;i<=m;++i)
{
std::cin>>a>>b;
ll w=read();
if(!p[a])p[a]=++n;
if(!p[b])p[b]=++n;
ll pa=p[a],pb=p[b];
g[pa][pb]=g[pb][pa]=min(g[pa][pb],w);
e.push_back(Edge(pa,pb,w));
}
std::sort(e.begin(),e.end());
ll cnt=0,k=read();
Kru();
for(ll i=2;i<=n;++i)
if(g[1][i]!=INF)
{
ll rt=s.find(i);
if(dis[rt]>g[1][i])
{
dis[rt]=g[1][i];
out[rt]=i;
}
}
for(ll i=2;i<=n;++i)
if(dis[i]!=INF)
{
--k;
ans+=dis[i];
used[1][out[i]]=used[out[i]][1]=1;
}
while(k--)
{
memset(maxe,0,sizeof maxe);
dfs(1);
ll cur=0,v=0;
for(ll i=2;i<=n;++i)
if(g[1][i]&&!used[1][i]&&maxe[i].w-g[1][i]>cur)
cur=maxe[i].w-g[1][i],v=i;
if(cur<=0)break;
ans-=cur;
used[maxe[v].u][maxe[v].v]=used[maxe[v].v][maxe[v].u]=0;
used[1][v]=used[v][1]=1;
}
printf("Total miles driven: %lld",ans);
return 0;
}