HDU 6041 I Curse Myself(点双联通加集合合并求前K大） 2017多校第一场

题意：

给出一个仙人掌图，然后求他的前K小生成树。

思路：

先给出官方题解

由于图是一个仙人掌，所以显然对于图上的每一个环都需要从环上取出一条边删掉。所以问题就变
为有 M 个集合，每个集合里面都有一堆数字，要从每个集合中选择一个恰好一个数加起
来。求所有的这样的和中，前 K 大的是哪些。这就是一个经典问题了。

点双联通就不说了都一眼能看出来做法就是缩点之后每个环每次取一个，然后找最大的k个所以这道题的难点就在这里，做法当然是不知道啦，看了题解和博客才懂的。以前做过两个集合合并的，这个是k个合并，和两个集合合并差不多，不过感觉很厉害啊。。就是先两个合并，然后和第三个合并，在和第四个，然后就可以了。。复杂度的话题解说的O（KM）。。。那就O（KM）吧，反正这个是真不会证过程挺厉害的在合并的时候

void merge(vector<int> &V , vector<int> B) {

   priority_queue< opt > Q;

   for (int i = 0 ; i < B.size() ; ++ i) {

       Q.push((opt) {V[0] + B[i] , i , 0});

   }

   W.resize(0);

   while (W.size() < K && !Q.empty()) {

       auto it = Q.top(); Q.pop();

       W.push_back(it.w);

       if (it.y + 1 < V.size()) {

           ++ it.y;

           Q.push((opt) {B[it.x] + V[it.y] , it.x , it.y});

       }

   }

   V = W;

}

最开始一直没看懂看了一天呀。。。后来想通了感觉还是挺简单的，然后在本机跑，没开O2跑了大半辈子。。。

具体过程其实就是对于每个已经合并了的数组，最开始让他最大的和B数组合并，然后对于已经合并了的数组，如果当前

的这一位被push进答案数组，那么就把先合并数组的次大的和B数组的当前数字合并就可以了。

思路挺厉害的~

代码就贴标程的吧～

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n , m , K;

struct opt {

    int w , x , y;

    bool operator < (const opt& R) const {

        return w < R.w;

    }

};

vector<int> W;

void merge(vector<int> &V , vector<int> B) {

    priority_queue< opt > Q;

    for (int i = 0 ; i < B.size() ; ++ i) {

        Q.push((opt) {V[0] + B[i] , i , 0});

    }

    W.resize(0);

    while (W.size() < K && !Q.empty()) {

        auto it = Q.top(); Q.pop();

        W.push_back(it.w);

        if (it.y + 1 < V.size()) {

            ++ it.y;

            Q.push((opt) {B[it.x] + V[it.y] , it.x , it.y});

        }

    }

    V = W;

}

int pre[N] , mcnt;

struct edge {

    int x , w , next;

} e[N << 2];

vector<int> res;

int dfn[N] , low[N] , ncnt;

stack<int> S;

void dfs(int x , int fa) {

    dfn[x] = low[x] = ++ ncnt;

    for (int i = pre[x] ; ~i ; i = e[i].next) {

        int y = e[i].x;

        if (!dfn[y]) {

            S.push(i);

            dfs(y , i ^ 1);

            low[x] = min(low[x] , low[y]);

            if (low[y] > dfn[x]) {}//(x , y) is bridge

            if (low[y] >= dfn[x]) {

                int j;

                vector<int> V;

                do {

                    j = S.top();

                    S.pop();

                    V.push_back(e[j].w);

                } while (j != i);

                if (V.size() > 1) {

                    //cout << V.size() << endl;

                    //for (auto &x : V) cout << x << ' '; cout << endl;

                    merge(res , V);

                }

            }

        } else if (i != fa && dfn[y] < dfn[x])

            S.push(i) , low[x] = min(low[x] , dfn[y]);

    }

}

void work() {

    memset(pre , -1 , sizeof(pre));

    mcnt = ncnt = 0;

    int sum = 0;

    for (int i = 0 ; i < m ; ++ i) {

        int x , y , z;

        scanf("%d%d%d" , &x , &y , &z);

        e[mcnt] = (edge) {y , z , pre[x]} , pre[x] = mcnt ++;

        e[mcnt] = (edge) {x , z , pre[y]} , pre[y] = mcnt ++;

        sum += z;

    }

    scanf("%d" , &K);

    res.resize(0);

    res.push_back(0);

    memset(dfn , 0 , sizeof(dfn));

    dfs(1 , 0);

    int w = 0;

    for (int i = 0 ; i < res.size() ; ++ i) {

        w += (i + 1) * (sum - res[i]);

    }

    static int ca = 0;

    printf("Case #%d: %u\n" , ++ ca , w);

}

int main() {

    res.reserve(100001);

    W.reserve(100001);

    while (~scanf("%d%d" , &n , &m)) {

        work();

    }

    return 0;

}

巴特西

HDU 6041 I Curse Myself(点双联通加集合合并求前K大） 2017多校第一场

最新文章

热门文章