题目描述
从前有一个基于一张无向图的游戏,我个人认为是比较无聊,但是出题需要,还是给你们讲讲怎么玩吧。= = 给一张地图,地图上有一些城市,城市之间可能有线路连通,我们用一个无向图来表示以简化概念,每条边有个权值,表示选择这条边需要花费的费用。给定4对顶点(可能重复),求一个权值最小的边集,使得任意一对顶点可以由选出的边集中的边相连。 按照惯例,下面给出一个例子:
输入格式
第1行2个整数,n和m,分别表示城市的个数和边的个数。
接下来n行,每行一个字符串,表示每个城市的名字。城市的名字为一个不超过20个字
符,由小写字母构成的字符串。
再接下来m行,每行给出s1,s2和w,其中s1,s2为城市的名字,w为他们之间边的权值。
最后,给出4行,每行给出两个字符串,分别为要求的一对城市的名字。
输出格式
一行,输出最小的花费。
样例
样例输入:
2 1
first
second
first second 10
first first
first first
second first
first first
样例输出:
10
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\n",dp[st-1]);
- return 0;
- }