Hdu 5452 Minimum Cut (2015 ACM/ICPC Asia Regional Shenyang Online) dfs + LCA

题目链接：

题目描述：

　　有一棵生成树，有n个点，给出m-n+1条边，截断一条生成树上的边后，再截断至少多少条边才能使图不连通，问截断总边数？

解题思路：

　　因为只能在生成树上截断一条边(u, v)，所以只需要统计以v为根节点的子生成树里的节点与子生成树外的节点的边数就可以了。对于新加入的边(u', v')来说，只影响以LCA(u, v)为根节点的子树里面的节点。统计所有答案，扫一遍输出最小即可。(比赛的时候只统计叶子节点，给水过去了........23333333)

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 struct node

 {

     int to, next;

 }edge[maxn*];

 int tot, head[maxn], deep[maxn], fa[maxn], ans[maxn];

 void init ()

 {

     tot = ;

     memset (head, -, sizeof(head));

 }

 void Add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot ++;

 }

 void dfs (int u, int father, int dep)

 {

     deep[u] = dep;

     ans[u] = ;

     fa[u] = father;

     for (int i=head[u]; i!=-; i=edge[i].next)

     {

         int v = edge[i].to;

         if (v != father)

             dfs (v, u, dep+);

     }

 }

 void LCA (int x, int y)

 {

     while (x != y)

     {

        if (deep[x] >= deep[y])

        {

            ans[x] ++;

            x = fa[x];

        }

        else

        {

            ans[y] ++;

            y = fa[y];

        }

     }

 }

 int main ()

 {

     int t, n, m, i;

     scanf ("%d", &t);

     for (int j=; j<=t; j++)

     {

         init ();

         int u, v;

         scanf ("%d %d", &n, &m);

         for (i=; i<n; i++)

         {

             scanf ("%d %d", &u, &v);

             Add (u, v);

             Add (v, u);

         }

         dfs (, , );

         for ( ;i<=m; i++)

         {

             scanf ("%d %d", &u, &v);

             LCA (u, v);

         }

         int res = INF;

         for (i=; i<=n; i++)

             res = min (res, ans[i]);

         printf ("Case #%d: %d\n", j, res);

     }

     return ;

 }

巴特西

Hdu 5452 Minimum Cut (2015 ACM/ICPC Asia Regional Shenyang Online) dfs + LCA

最新文章

热门文章