2020超级码力复赛-B

2020超级码力复赛-B

十月 03, 2020

吃鸡

题意

给出n<1e5个点m<2e5条边

k<5个特殊点,求将k个点联通的最小边权和 (最小图)

​

题解

斯坦纳树模板题

斯坦纳树参考博客

将k个点状态压缩 利用dp转移 得到答案

状态压缩:比如5个点用二进制表示是否纳入集合10111表示除第2个点外都纳入集合 

1
2
3
4
5
for 总状态集 from 0 to 1<<k
	for 根结点 from 1 to n
		for 子状态集合 
			dp[总状态集][根节点]=min(self,dp[子状态集A][根节点]+dp[子状态集B][根节点])
	ShoutCut(总状态集时的最短路)

ShoutCut算法可以用spfa或迪捷斯卡特

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
typedef long long ll;
//#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,int>
const ll Max=3e5+5;
const ll Mod=998857459;
const int inf=0x3f3f3f3f;

/*
*/

class Solution {
public:
    /**
     * @param n: n islands
     * @param k: k special islands
     * @param m: The number of the two islands and the time spent crossing the bridge connecting the two islands
     * @return: Time spent on the bridge through all the small islands
     */
    bool vis[Max];
    vector<P>mp[Max];
    ll dp[(1<<5)+5][Max];
    void ShoutCut(ll* dis,int n){
        priority_queue<P,vector<P>,greater<P> >q;
        for(int i=1;i<=n;i++){
            if(dis[i]!=inf)q.push({dis[i],i});
            vis[i]=0;
        }
        while(!q.empty()){
            P point=q.top();
            q.pop();
            int now=point.second;
            if(vis[now])continue;
            vis[now]=1;
            for(auto to:mp[now]){
                if(dis[to.first]>dis[now]+to.second){
                    dis[to.first]=dis[now]+to.second;
                    q.push({dis[to.first],to.first});
                }
            }
        }
    }
    long long cost(int n, vector<int> &k, vector<vector<int>> &m) {
        int Kland=k.size();
        for(auto edge:m){
            int u=edge[0],v=edge[1],w=edge[2];
            mp[u].push_back({v,w});
            mp[v].push_back({u,w});
        }
        memset(dp,inf,sizeof dp);
        ///注意初始化源点
        for(int i=0;i<Kland;i++)dp[1<<i][k[i]]=0;
        for(int S=1,up=1<<Kland;S<up;S++){
            ///S的二进制状态表示第i个点是否被加入初始集合S
            for(int start=1;start<=n;start++){
                ///枚举以start作为根节点到所有被纳入集合的关键点
                ///注意最短路中的源点和此处遍历的根节点不同
                for(int S0=S&(S-1);S0;S0=S&(S0-1)){ 
                    ///这个遍历表示逐个将S其中一个1换成0
                    /// 比如S=11010 那S0= 11000，10010，01010
                    ///从两个子状态集合转移到当前状态集
                    dp[S][start]=min(dp[S][start],dp[S0][start]+dp[S^S0][start]);
                    
                }
            }
            ///当前状态集被更新(松弛完)后再作为最短路的源点为下次转移做准备
            ShoutCut(dp[S],n);
        }
        return dp[(1<<Kland)-1][k[0]];
    }
};