双联通分量

HDU 6041 I Curse Myself

Posted on

多校第一场的小锅,因为就算给我时间我也写不出来的题……算是小锅吧,还有三个大锅在背上。

开头先说一声,薛昊这个坑比,woc,跟我说这里的k小生成树是就是先取一个最小的,连上每一条边……

然后我在用优先队列的时候我就真的先推小的……
md debug好久才发现……醉了。

题意:
给你一个仙人掌图,要你求出前k小的生成树。将之与k相乘求和 mod 2 ^ 32

思路:
如果是一个一般图,那问题将非常困难,但他是一个仙人掌图,对于一个生成树来说,整张图的桥必定不能删掉,所以必须从每一个环中删掉一条边,而我们删掉的边要求前k大。

将每一个环的边作为集合,多个集合合并,求出前k大,这是一个经典问题。

方法是对每两个集合两两合并,将两个集合的边各自相连,用优先队列推出前k大,但这样时间和空间复杂度都很高。

一个与优先队列思想相似并且简单的方法就是,我们将旧集合维护有序,在这里为降序,并用一个优先队列存储两集合权值和。
首先将新集合的每个元素与旧集合最大元素(就是首位置)相加并加入队列。每次推出一个最大元素的时候,都将这个最大元素在新集合的原元素与旧集合相应元素的下一个元素相加加入队列。
以此推出k个元素存入集合。

这里写的是暴力求解法,tarjan求解接近tle边缘……

这里有个小技巧,就是我们要对结果取 2^ 32 膜 , 值得注意的是 int 存储的总数就是 2 ^ 32 ,而 unsighed int 的范围则刚好是 [ 0 , 2 ^ 32) 所以我们只要用一个int存储,输出 用 %u 就会为我们自动按要求取 膜 。这应该是出题人特意设置的。但的确很妙。

AC Code

#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int max_n = 1010;
const int max_k = 1e5 + 5;
int n, m, k, idx, sum, cnt;
int head[max_n], fa[max_n], dep[max_n], eval[max_n], down[max_n];
int dsu[max_n];

int roll[3][max_k], cur, pre = 1;

struct Edge {
    int to, next, weight;
    Edge() {}
    Edge(int _to, int _next, int _weight) { to = _to, next = _next, weight = _weight; }
} edges[max_n << 1];

struct NonTreeEdge {
    int from, to, weight;
    NonTreeEdge() {}
    NonTreeEdge(int _from, int _to, int _weight) { from = _from, to = _to, weight = _weight; }
} NTedges[max_n];

struct node {
    int val, pos;
    node() {}
    node(int _val, int _pos) { val = _val, pos = _pos; }
    bool operator<(const node& a) const { return val < a.val; }
};

priority_queue<node> que;

int addEdge(int u, int v, int w)
{
    edges[idx] = Edge(v, head[u], w);
    head[u] = idx++;
    edges[idx] = Edge(u, head[v], w);
    head[v] = idx++;
    return 0;
}

int dsuFind(int u) { return dsu[u] < 0 ? u : dsu[u] = dsuFind(dsu[u]); }

bool dsuMerge(int u, int v)
{
    u = dsuFind(u), v = dsuFind(v);
    if (u == v)
        return false;
    dsu[u] = v;
    return true;
}

void dfs(int u)
{
    for (int id = head[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (v == fa[u])
            continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        eval[v] = edges[id].weight;
        dfs(v);
    }
}

inline void read(int& x)
{
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main()
{
    int u, v, w, cas = 0;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(head, -1), fill(dsu, -1), idx = cnt = sum = 0;
        while (m--) {
            read(u), read(v), read(w);
            sum += w;
            dsuMerge(u, v) ? addEdge(u, v, w) : (NTedges[cnt++] = NonTreeEdge(u, v, w), 1);
        }
        dfs(1);
        read(k);
        roll[cur][0] = 1, roll[cur][1] = 0;
        for (int id = 0; id < cnt; id++) {
            int u = NTedges[id].from, v = NTedges[id].to, &sz = roll[2][0] = 1;
            roll[2][1] = NTedges[id].weight;
            while (dep[u] > dep[v])
                roll[2][++sz] = eval[u], u = fa[u];
            while (dep[u] < dep[v])
                roll[2][++sz] = eval[v], v = fa[v];
            while (u != v) {
                roll[2][++sz] = eval[u];
                roll[2][++sz] = eval[v];
                u = fa[u], v = fa[v];
            }
            cur ^= 1, pre ^= 1;
            while (!que.empty())
                que.pop();
            for (int i = 1; i <= sz; i++) {
                down[i] = 1;
                que.push(node(roll[2][i] + roll[pre][1], i));
            }
            for (int& i = roll[cur][0] = 0; i < k && !que.empty();) {
                int val = que.top().val, pos = que.top().pos;
                que.pop();
                roll[cur][++i] = val;
                if (down[pos] < roll[pre][0]) {
                    val = roll[2][pos] + roll[pre][++down[pos]];
                    que.push(node(val, pos));
                }
            }
        }
        int ans = 0;
        for (int i = roll[cur][0], tmp = 0; i > 0; i--) {
            tmp += sum - roll[cur][i];
            ans += tmp;
        }
        printf("Case #%d: %u\n", ++cas, ans);
    }
    return 0;
}
双联通分量

算法学习——求割点与桥的tarjan算法 HDU4738

Posted on

前天打周赛做到 HDU4738 绞尽脑汁都没想到用什么好的方法来解决这个问题 周赛结束之后跟Yasola和xcy讨论了一下居然用到 tarjan算法 exm??? tarjan不是用来求 lca的么???

回去怒补了一发才知道 tarjan原来是一系列是算法 根据我看到的博客原文 可以这么说 tarjan是个天才 他伟大的一生创造了无数的算法 统称 tarjan算法 其中有三个最有名的 求lca 求图的割点与桥 (还有一个啥来着 反正我最近一定要学一下 无奈看完之后就断电熄灯了 一直拖到昨晚才学

基本概念:

图论里的桥 即 连接两个子图唯一边 如果这条边被你砍了 整个图将被你一分为二

图论里的割点 同桥的理解 只是对象是一个结点 如果这个结点被你分开 那么整个图也将分裂

因为我也是刚学 hdu4738 的对象也是一张无向图 以下均以无向图进行讨论 有向图日后再说

在tarjan算法中 对于一张图 我以深搜为核心 并且每个节点只访问一次 那么最后深搜得到的图 会是什么??

是一棵树!! (这真是太奇妙了 我自认为对搜索有点信心 但是从来没有想过这样的应用

于是有如下定理:

在无向连通图G中

1.根结点为割点 当且仅当它有两个及以上的子结点

2.非根节点为割点 当且仅当 u 存在结点 v 及其所有后代都没有反向边可以返回 u 的祖先 (不包括 u

我们在深搜过程中每一个节点都有他的访问次序 我们定义一个 时间戳 dfn 来表示

另外我们还需要一个 定义一个 low 表示 该结点反向能达到的最小的 dfn ( 初始都是 low=dfn

虽然我们深搜出一棵树 但是我们的研究对象还是原图 对于原图来说 每一个结点都会有若干条边

如果在这时 我的结点 u 有一条到 v 的边 而且 low[v] <= dfn[u] 这就表示在 u 结点有一条边 可以返回到之前的结点 并形成一个环 那么显而易见 这根本不会是桥

相反 只要对每一个边访问 若 low[v] > dfn [u] 那么这条边即为 桥

大犇都是先理解割点再理解桥的 像我这种菜鸡只能从 割点的特殊情况桥 开始理解

对于割点的话道理 还是差不多 无非是一个 等号的问题

在判断桥中 如果 low[v]==dfn[u] 那么这意味着始末都是这个 u 结点的一个 环而已 (包括自环) 没什么影响 只要是环 那么必然不是桥

而对于割点 如果 low[v]==dfn[u] 那么v及其所有子结点都必须通过 u 结点来访问 u 的祖先 所以 u 仍然是割点

附带 HDU 4738 Caocao's Bridges

这题就是很裸的求桥的问题 只不过 求最短的桥 并且有两个坑点

我们在用tarjan 的时候吧每个桥都保存在一个数组中 最后for 一遍即可

而坑点包括

1.原图可能不联通 这时不需要派人去炸桥 直接输出 0

2.有重边

3.可能有权值为0的桥 但我们必须要有一个人去带炸弹啊 所以这是输出 1

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int n, m, indx, vis_time, union_num, ansn;
int head[maxn], low[maxn], dfn[maxn], ans[maxn];

struct node {
    int to;
    int next;
    int w;
};
node edge[2 * maxn * maxn];

void AddEdge(int u, int v, int w)
{
    edge[indx].to = v;
    edge[indx].w = w;
    edge[indx].next = head[u];
    head[u] = indx++;

    edge[indx].to = u;
    edge[indx].w = w;
    edge[indx].next = head[v];
    head[v] = indx++;
}

void init()
{
    vis_time = indx = ansn = 0;
    union_num = 1;
    memset(head, -1, sizeof head);
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
}

void tarjan(int u, int father)
{
    low[u] = dfn[u] = ++vis_time;
    int pre_num = 0;
    for (int id = head[u]; id != -1; id = edge[id].next) {
        int v = edge[id].to;
        if (v == father && pre_num == 0) {
            pre_num++;
            continue;
        }
        if (!dfn[v]) {
            union_num++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                ans[ansn++] = edge[id].w;
        } else if (dfn[v] < dfn[u])
            low[u] = min(low[u], dfn[v]);
    }
}

int main()
{
    int u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0)
            break;
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            AddEdge(u, v, w);
        }
        tarjan(1, 1);
        if (union_num < n)
            puts("0");
        else {
            int true_ans = inf;
            for (int i = 0; i < ansn; i++)
                if (true_ans > ans[i])
                    true_ans = ans[i];
            if (true_ans == 0)
                true_ans++;
            else if (true_ans == inf)
                true_ans = -1;
            printf("%d\n", true_ans);
        }
    }
    return 0;
}