2019 ICPC 南昌邀请赛 A-Attack（斯坦纳树）

墨蓝 2021-11-23 04:24 264阅读 0赞

## 题意：给出一个无向图，和四对数据。每对数据分别为图中的两个点。要求添加一些边，使每对点都能连通，让总边权最小。 ##

## 分析：POJ3123、NWERC2006原题，《acm国际大学生程序设计竞赛：题目与解读》P564。斯坦纳森林模板题，把所有的集合放在一起，做一遍斯坦纳树，然后对所有集合做一遍子集合并dp。斯坦纳树的转移方程有两重：第一重，先通过连通状态的子集进行转移。dp\[i\]\[state\]=min\{ dp\[i\]\[subset1\]+dp\[i\]\[subset2\] \} ，枚举子集的技巧可以用 for(sub=(state-1)&state;sub;sub=(sub-1)&state)。第二重，在当前枚举的连通状态下，对该连通状态进行松弛操作。dp\[i\]\[state\]=min\{ dp\[i\]\[state\], dp\[j\]\[state\]+e\[i\]\[j\] \}。复杂度 O(n\*3^k+c\*E\*2^k)。k为要求连通的点数，c为SPFA复杂度中的常数，E为边的数量，但几乎达不到全部边的数量，甚至非常小。3^k来自于子集的转移，sum\{C(i,n)\*2^i\} (1<=i<=n)，用二项式展开求一下和。 ##

## 斯坦纳树入门参考[https://www.cnblogs.com/ECJTUACM-873284962/p/7643445.html\#autoid-0-1-0][https_www.cnblogs.com_ECJTUACM-873284962_p_7643445.html_autoid-0-1-0]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    const int INF = 0x3f3f3f3f;
    
    int n, m, cnt, u, v, w;
    int status;///表示0~n号节点都被选择时的状态+1
    int s[40], nt[2009], e[2009], val[2009];
    int dis[40][1000], vis[40], ans[1000], flag[1000];
    ///dis[i][j]表示以i节点为根选择点集状态为j时的最小值；vis[i][j]表示i节点为点集j时是否在队列中
    queue<int>q;
    map<string, int>mp;/// 城市名和节点编号的对应关系
    char s1[30], s2[30];
    
    ///初始化
    void init()
    {
    	memset(vis, 0, sizeof vis);
    	memset(s, -1, sizeof s);
    	mp.clear();
    	cnt = 0;
    	status = 1 << 8;
    	for (int i = 1; i <= n; i++)
    		for (int j = 0; j < status; j++)
    			dis[i][j] = INF;
    }
    
    ///SPFA进行松弛
    void SPFA(int sta)
    {
    	while (!q.empty())
    	{
    		int pre = q.front();
    		q.pop();
    		vis[pre] = 0;
    		for (int i = s[pre]; ~i; i = nt[i])
    		{
    			if (dis[pre][sta] + val[i] < dis[e[i]][sta])
    			{
    				dis[e[i]][sta] = dis[pre][sta] + val[i];
    				if (!vis[e[i]])
    				{
    					vis[e[i]] = 1;
    					q.push(e[i]);
    				}
    			}
    		}
    	}
    }
    /// 斯坦纳树核心代码（状压dp）
    void Steiner_Tree()
    {
    	for (int i = 0; i < status; i++)
    	{
    	    /// 第一重，先通过连通状态的子集进行转移。
    	    /// dp[i][state]=min{ dp[i][subset1]+dp[i][subset2] }
    		for (int j = 1; j <= n; j++)
    		{
    			for (int k = i; k; k = (k - 1) & i)
    				dis[j][i] = min(dis[j][i], dis[j][k] + dis[j][i - k]);
    			if (dis[j][i] != INF)
    			{
    				q.push(j);
    				vis[j] = 1;
    			}
    		}
    		/// 第二重，在当前枚举的连通状态下，对该连通状态进行松弛操作。
    		/// dp[i][state]=min{ dp[i][state], dp[j][state]+e[i][j] }
    		SPFA(i);
    	}
    }
    
    /// 检查点对是否在k状态下的存在性是否一样 存在性不一致时返回真需要进行子集合并
    int check(int k)
    {
    	for (int i = 0; i < 4; i++)
    		if ((k >> i & 1) ^ (k >> (i + 4) & 1)) return 0;
    	return 1;
    }
    
    /// (斯坦纳森林解法）把所有的集合放在一起，做一遍斯坦纳树，然后对所有集合做一遍子集合并dp。
    int main()
    {
    	while (~scanf("%d %d", &n, &m) && (n + m))
    	{
    		init();
    		for (int i = 1; i <= n; i++) scanf("%s", s1), mp[s1] = i;
    		for (int i = 1; i <= m; i++)
    		{
    			scanf("%s%s%d", s1, s2, &w);
    			u = mp[s1], v = mp[s2];
    			nt[cnt] = s[u], s[u] = cnt, e[cnt] = v, val[cnt++] = w;
    			nt[cnt] = s[v], s[v] = cnt, e[cnt] = u, val[cnt++] = w;
    		}
    		for (int i = 1; i <= 8; i++) ///处理四对点对
    		{
    			scanf("%s", s1);
    			int temp = ((i & 1) ? i / 2 : i / 2 + 3); /// 0-4 1-5 2-6 3-7 一一对应
    			dis[mp[s1]][1 << temp] = 0;
    		}
    		Steiner_Tree();
    		/// 求出8个点（四个点对）都相连的花费
    		for (int i = 0; i < status; i++)
    		{
    			flag[i] = check(i), ans[i] = INF;
    			for (int j = 1; j <= n; j++) ans[i] = min(ans[i], dis[j][i]);
    		}
    
    		///合并子集
    		for (int i = 0; i < status; i++)
    			if (flag[i])///需要合并时
    			{
    			    ///枚举子集转移
    				for (int j = i; j; j = (j - 1)&i)
    					if (flag[j] && flag[i - j]) ///转移条件
                            ans[i] = min(ans[i], ans[j] + ans[i - j]);
    			}
    		printf("%d\n", ans[status - 1]);
    	}
    	return 0;
    }

[https_www.cnblogs.com_ECJTUACM-873284962_p_7643445.html_autoid-0-1-0]: https://www.cnblogs.com/ECJTUACM-873284962/p/7643445.html#autoid-0-1-0