强联通分量

算法学习—— tarjan算法求强连通分量 (附带 hdu1827

Posted on

tarjan算法的第三个应用 求强连通分量

强连通分量我就不具体介绍了

这次的关键数组含义仍然没变 low[u] 仍然还是 u 能到达的最小的 low[v] ( low[v] 又由它最小的 low[v'] 决定

这里有个很关键的点 low[u] == dfn[u] 若以 求割点与桥的tarjan理解 表示 u 的子树的结点中最早能返回到 u,不能访问到u的祖先, 而 u 又必然能访问到 其子树,因此很简容易便能理解 u 及其子树形成了一个最大的连通块 即 强连通分量

而根据 dfs 的 递归与回溯特性 我们以一个栈来存储一个强连通分量 当得到 low[u]==dfn[u] 时可以逐个出栈得到强连通中的所有结点

鉴于强连通的特性 我们可以将算法简单优化一下 比如 不在 连通栈中的结点 我们已经无需去更新它的 low[u]

HDU 1827 Summer Holiday

ac code

这题的话 tarjan算法求一下缩点 并且吧强连通分量中最小的值记录下来 最后计算下入度为0 的点 加上即可(一开始我还想用并查集 还是太嫩了…………

/* ***********************************************************************
   > File Name: contest.cpp
   > Author: Key
   > Mail: keyld777@gmail.com
   > Created Time: 2016年11月18日 星期日 20时10分38秒
 ********************************************************************** */
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int n, m, indx, vis_time, ansn, scn, top;
int head[maxn], low[maxn], dfn[maxn], stack[maxn], val[maxn], color[maxn], minval[maxn];
int in[maxn];
bool instack[maxn];

struct node {
    int from;
    int to;
    int next;
    // int w;
};

node edge[2 * maxn];

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

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

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = ++vis_time;
    instack[u] = true;
    stack[++top] = u;
    for (int id = head[u]; id != -1; id = edge[id].next) {
        v = edge[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scn++;
        minval[scn]=val[u];
        do {
            v = stack[top--];
            instack[v] = false;
            color[v] = scn;
            minval[scn]=min(minval[scn],val[v]);
        } while (v != u);
    }
}

int main()
{
    int u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", val + i);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            AddEdge(u, v);
        }
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                tarjan(i);
        for (int i = 0; i < m; i++) {
            u = edge[i].from;
            v = edge[i].to;
            if (color[u] != color[v])
                in[color[v]]++;
        }
        int ans=0,ansn=0;
        for(int i=1;i<=scn;i++)
            if(in[i]==0){
                ansn++;
                ans+=minval[i];
            }
        printf("%d %d\n",ansn,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;
}
哈夫曼树

哈夫曼编码

Posted on

传送门

OJ小作业 很久以前第一次听说哈夫曼树问了一下煞笔室友 听他很不屑地说 只是一个贪心而已 我也就没怎么在意

最近李总上课点名不得不去上一下 可惜也只是到那里发了一下呆 点了一下到就过去了 他在讲哈夫曼编码的时候我也没去听

搞得我刚开始看到这题的时候有点小蒙蔽 还好数据比较水 不然估计要卡很长时间 (因为完全是我根据以前的知识xjb搞的 还好还好是一A

下面是源码+注解 (因为完全是自己看了远离后搞得 可能有点烦........

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

#define root tree[id]
#define leson tree[ldir]
#define rison tree[rdir]

using namespace std;
const int maxn = 104;
int len, all_time;
int tree_root;//根节点
char to_c[maxn];//由节点的值转化为字符
char tar[maxn * 100];
char tar_ch;//当前目标字符
char output[maxn];//输出数组
bool flag;//标记  如果已经输出就直接返回

struct node {
    int lson, rson;
    int tim;//结点生成时间  所有原结点初始化为0
    int order;//节点编号
    int val;//结点的值
    bool operator<(const node& a) const
    {
        if (val != a.val)
            return val > a.val;
        if (tim != a.tim)
            return tim > a.tim;
        return order > a.order;
    }//按照题意出队
};

priority_queue<node> que;
node tree[maxn << 2];

int CreatTree()
{
    node ta, tb;
    int id;
    while (que.size() > 1) {
        ta = que.top();
        que.pop();
        tb = que.top();
        que.pop();
        id = len + all_time;
        root.lson = ta.order;
        root.rson = tb.order;
        root.val = ta.val + tb.val;
        root.order = id;
        root.tim = all_time++;
        que.push(root);
        // printf("%d %d\n",ta.order,tb.order);
    }//取出两个节点并合并再入队   最后剩余的便是根节点
    ta = que.top();
    que.pop();
    return ta.order;
}

void lock(int id, int dep)
{
    if (flag)//若已经输出过了   就直接返回
        return;
    int ldir = root.lson, rdir = root.rson;
    if (ldir) {
        output[dep] = '0';
        lock(ldir, dep + 1);
    }
    if (rdir) {
        output[dep] = '1';
        lock(rdir, dep + 1);
    }
    if (!ldir && !rdir && to_c[root.order] == tar_ch) {  //确保该结点为叶子结点也可以省点时间
        for (int i = 0; i < dep; i++)
            putchar(output[i]);
        flag = true;//标记为true
    }
}

int unlock(int index)
{
    int id = tree_root;
    while (root.lson || root.rson) {
        if (tar[index] == '0')  // 0 向左 1向右
            id = root.lson;
        else
            id = root.rson;
        index++;
    }
    putchar(to_c[root.order]);
    return index;//返回转化后的index
}

int main()
{
    while (scanf("%s", to_c + 1) != EOF) {
        len = strlen(to_c + 1);
        for (int id = 1; id <= len; id++) {
            scanf("%d", &root.val);
            root.order = id;
            root.tim = 0;
            root.lson = root.rson = 0;
            que.push(root);
        }
        all_time = 1;
        tree_root = CreatTree();
        // printf("root: %d\n",tree_root);
        // for(int id=1;id<=tree_root;id++)
        //    printf("order: %d  val: %d  lson: %d  rson:%d\n",root.order,root.val,root.lson,root.rson); //可取消注释查看建树是否正确
        scanf("%s", tar);
        int tar_len = strlen(tar);
        for (int i = 0; i < tar_len; i++) {
            tar_ch = tar[i];
            flag = false;
            lock(tree_root, 0);
        }
        puts("");
        scanf("%s", tar);
        tar_len = strlen(tar);
        int i = 0;
        while (i < tar_len)
            i = unlock(i);
        puts("");
    }
    return 0;
}
DFS

HDU 4405 Aeroplane chess

Posted on

昨天周赛的水搜索 然而………………

因为昨晚基地灯坏了,只能跟寝室里的煞笔一起打(当然他比我强,他10分钟A了 我越写越急

最后写了两个小时………………

不想多说什么了 先贴上源代码 再分析优化

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

using namespace std;
char str[20];
int flag[20];
int len, ans;

bool judge()
{
    int mid;
    for (mid = 0; mid < len; mid++)
        if (flag[mid] == 2)
            break;
    if (mid == len)
        return false;
    long long lans = str[0] - '0', rans = str[mid] - '0', i;
    for (i = 1; i < mid; i++)
        if (flag[i])
            break;
        else
            lans = lans * 10 + str[i] - '0';
    while (i < mid) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        lans += tmp;
    }
    for (i = mid + 1; i < len; i++)
        if (flag[i])
            break;
        else
            rans = rans * 10 + str[i] - '0';
    while (i < len) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        rans += tmp;
    }
    return lans == rans;
}

void dfs(int pos, bool has_equal)
{
    if (pos == len) {
        if (has_equal && judge())
            ans++;
        return;
    }
    if (has_equal) {
        flag[pos] = 1;
        dfs(pos + 1, true);
        flag[pos] = 0;
        dfs(pos + 1, true);
    } else {
        flag[pos] = 0;
        dfs(pos + 1, false);
        flag[pos] = 1;
        dfs(pos + 1, false);
        // if(pos==len-1) return;
        flag[pos] = 2;
        dfs(pos + 1, true);
    }
}

int main()
{
    while (scanf("%s", str) != EOF) {
        if (strcmp(str, "END") == 0)
            break;
        len = strlen(str), ans = 0;
        memset(flag, 0, sizeof flag);
        flag[len] = 1000;
        dfs(1, false);
        printf("%d\n", ans);
    }
    return 0;
}

我当时的思路很明显了 先用DFS放置所有 + = 的位置 到最后判断一些能不能使等式成立

因为前面想的少,搞得后面的bug处理特别多

尤其是判断那里

对于优化建议

1.完全可以预处理一下 比如定义一个二维数组 num[27][27] 用num[x][y]表示 x-y 的数字 然后只要判断加号位置就好了

2.另外的话可以以一个循环判断=的位置 再对左右按序DFS 即可

好吧 我已经理论优化了

最后想说的是 打ACM 心态很重要 心态爆炸了 这场基本也是完了