本来以为是一道好题……

没想到xjb被我水过去了……

题目看不大懂去找题解看题意,都说什么LCA,醉了……真的不喜欢数据弱的题目。

题意:
给你一棵生成树,再多给你几条边,要你只能删除一条生成树的边的同时,最少删掉多少条边才能使得整张图图不联通。

思路:
一个很显然的规律就是,找到生成树上度数为1的点,再比较其他度数和即可……

这里有个漏洞,就是可以在删掉一条生成树上的边就可以分割整张图,简单说,就是桥……

不是很懂他们LCA的思路,水过了就不想思考了。我倒是觉得,直接tarjan缩点预处理一下,再特判一下缩点后的点数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#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 maxn = 2e4 + 5;
const int maxm = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int tree_degree[maxn];
int degree[maxn];
int n, m;

int main()
{
    int T, u, v;
    scanf("%d", &T);
    each(cas, T)
    {
        scanf("%d %d", &n, &m);
        fill(tree_degree, 0), fill(degree, 0);
        int ans = inf;
        each(i, n - 1) scanf("%d %d", &u, &v), tree_degree[u]++, tree_degree[v]++;
        each(i, m - n + 1) scanf("%d %d", &u, &v), degree[u]++, degree[v]++;
        range(i, 1, n) if (tree_degree[i] == 1) ans = min(ans, 1 + degree[i]);
        printf("Case #%d: %d\n", cas + 1, ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

强联通分量

HDU 6165 FFF at Valentine

好烦,感觉自己的图论知识都有了,但是一旦写起来还是非常欠缺…… 什么时 Read more…

强联通分量

Kosaraju算法入门 ( 附 POJ 2186

算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一 Read more…

强联通分量

HDU 6073 Matching In Multiplication

今天多校的第一锅…… 这套题真是神奇,明明都是Claris出的,涉及图 Read more…