地图游戏

题目描述

从前有一个基于一张无向图的游戏，我个人认为是比较无聊，但是出题需要，还是给你们讲讲怎么玩吧。= = 给一张地图，地图上有一些城市，城市之间可能有线路连通，我们用一个无向图来表示以简化概念，每条边有个权值，表示选择这条边需要花费的费用。给定4对顶点(可能重复)，求一个权值最小的边集，使得任意一对顶点可以由选出的边集中的边相连。按照惯例，下面给出一个例子：

输入格式

第1行2个整数，n和m，分别表示城市的个数和边的个数。

接下来n行，每行一个字符串，表示每个城市的名字。城市的名字为一个不超过20个字

符，由小写字母构成的字符串。

再接下来m行，每行给出s1,s2和w，其中s1,s2为城市的名字，w为他们之间边的权值。

最后，给出4行，每行给出两个字符串，分别为要求的一对城市的名字。

输出格式

一行，输出最小的花费。

样例

样例输入：

2 1

first

second

first second 10

first first

second first

first first

样例输出：

Sol

斯坦纳树模板题，合并一下联通关系就好啦！

Code

#include <bits/stdc++.h>
using namespace std;
int las[10005],nex[10005],Arrive[10005],qz[10005],cnt,K;
int Bit[100005];
bool pd[100005];
int bel[100005],Size[100005],Temp;
int Lt[505][505];
int dis[100005][205];
int Id[100005];
int x[105],y[105];
bool vis[10005][205];
map<string,int> qwq;
void jt(int x,int y,int z)
{
cnt++;
nex[cnt]=las[x];
las[x]=cnt;
Arrive[cnt]=y;
qz[cnt]=z;
}
queue<pair<int,int> >que;
int dp[10005];
int N,M;
void SPFA()
{
while (!que.empty())
{
int u=que.front().first;
int d=que.front().second;
que.pop();
vis[u][d]=false;
for (int i=las[d];i;i=nex[i])
{
int v=Arrive[i];
if (dis[u|Id[v]][v]>dis[u][d]+qz[i])
{
dis[u|Id[v]][v]=dis[u][d]+qz[i];
if (!vis[u|Id[v]][v])
{
que.push(make_pair(u|Id[v],v));
vis[u|Id[v]][v]=true;
}
}
}
}
return;
}
int main()
{
memset(dis,63,sizeof(dis));
int INF=dis[0][0];
scanf("%d%d",&N,&M);
string s1;
for (int i=1;i<=N;i++)
{
cin>>s1;
qwq[s1]=i;
}
for (int i=1;i<=M;i++)
{
string s1,s2;
int w;
cin>>s1>>s2>>w;
jt(qwq[s1],qwq[s2],w);
jt(qwq[s2],qwq[s1],w);
}
int cntt=0;
string s2;
for (int i=1;i<=4;i++)
{
int u,v;
cin>>s1;
u=qwq[s1];
cin>>s2;
v=qwq[s2];
if (u==v)continue;
if (bel[u]&&bel[v]){
int upd=bel[v];if (bel[u]==bel[v])continue;
for (int i=1;i<=Size[upd];i++)
Lt[bel[u]][++Size[bel[u]]]=Lt[upd][i],bel[Lt[upd][i]]=bel[u];
Size[upd]=0;
}
else if (bel[u]||bel[v]){
if (bel[v])
swap(u,v);
bel[v]=bel[u];
Lt[bel[u]][++Size[bel[u]]]=v;
}
else {
bel[u]=bel[v]=++cntt;
Lt[cntt][++Size[cntt]]=u;Lt[cntt][++Size[cntt]]=v;
}
}
for (int i=1;i<=N;i++)
if (bel[i])
{
Temp++;
Id[i]=(1<<(Temp-1));
dis[Id[i]][i]=0;
}
else dis[0][i]=0;
int st=1<<Temp;
for (int ST=0;ST<st;ST++)
{
for (int i=1;i<=N;i++)
{
for (int mst=(ST-1)&ST;mst;mst=(mst-1)&ST)
dis[ST][i]=min(dis[ST][i],dis[mst|Id[i]][i]+dis[(ST-mst)|Id[i]][i]);
if (dis[ST][i]<INF&&!vis[ST][i])
que.push(make_pair(ST,i)),vis[ST][i]=true;
}
SPFA();
}
memset(dp,63,sizeof(dp));
for (int i=1;i<=N;i++)
for (int j=0;j<=st;j++)
dp[j]=min(dis[j][i],dp[j]);
int Ncnt=cntt;
cntt=0;
for (int i=1;i<=Ncnt;i++)
{
if (Size[i])
{
cntt++;
for (int j=1;j<=Size[i];j++)
Bit[cntt]|=Id[Lt[i][j]];
pd[Bit[cntt]]=true;
}
}
dp[0]=0;
for (int i=0;i<st;i++)
for (int j=i;j;j=(j-1)&i)
if (pd[j]&pd[i-j])
pd[i]=true;
for (int i=0;i<st;i++)
if (pd[i])
for (int j=i;j;j=(j-1)&i)
if (pd[j]) dp[i]=min(dp[i],dp[i-j]+dp[j]);
printf("%d ",dp[st-1]);
return 0;
}