首页 > ACM题库 > HDU-杭电 > HDU 3002-King of Destruction-连通性问题-[解题报告]HOJ
2014
02-26

HDU 3002-King of Destruction-连通性问题-[解题报告]HOJ

King of Destruction

问题描述 :

Zhou xingxing is the successor of one style of kung fu called "Karate Kid".he is falling love with a beautiful judo student,after being humiliated by her boyfriend,a Taekwando master from Japan,Zhou is going to fight with his rival in love.The way they fight is to destroy the wooden plank between some wooden pegs,in order to cut these wooden pegs into two disconnected parts,and destroy each piece of plank need consume different energy.However Zhou xingxing is beginner after all,so he is turn to you for help,please calculate the minimum energy he need to destroy the wooden plank.

输入:

The input consists of multiple test cases.
Each test case starts with two integers n (0 < n <= 100) and m in one line, where n、m are the number of wooden pegs and wooden plank.
Following are m lines, each line contains three integers s, e and q (0 <= s, e < n,q > 0), meaning that there need q energy to destroy the wooden plank between s and e.

输出:

The input consists of multiple test cases.
Each test case starts with two integers n (0 < n <= 100) and m in one line, where n、m are the number of wooden pegs and wooden plank.
Following are m lines, each line contains three integers s, e and q (0 <= s, e < n,q > 0), meaning that there need q energy to destroy the wooden plank between s and e.

样例输入:

2 1
0 1 50
3 2
0 1 50
1 2 10

样例输出:

50
10

还是一道很典型的求最小割的值,算法依旧。

这次做这道题,我模拟了一下算法实行,发现这个模板在对点删除的处理上很巧妙。通过这次研究,算法大致的步骤和实现方法,我已经知道是怎么样的流程,但是具体的证明之类的还是很迷糊。

代码如下:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
const int INF = 0x3fffffff;
int n, m;
int g[N][N], v[N], d[N];

int Stoer_wagner() 
{
    bool vis[N];
    int i, j, res = INF;
    for ( i = 0; i < n; ++i ) v[i] = i;
    while ( n > 1 ) {
        int maxp = 1, prev = 0;
        for ( i = 1; i < n; ++i ) {
            d[v[i]] = g[v[0]][v[i]];
            if ( d[v[i]] > d[v[maxp]] ) maxp = i;
        }
        memset( vis, 0, sizeof(vis) );
        vis[v[0]] = true;
        for ( i = 1; i < n; i++ ) {
            if ( i == n-1 ) {
                res = min( res, d[v[maxp]] );
                for ( j = 0; j < n; ++j ) {
                    g[v[prev]][v[j]] += g[v[j]][v[maxp]];
                    g[v[j]][v[prev]] = g[v[prev]][v[j]];
                }
                v[maxp] = v[--n];
            }
            vis[v[maxp]] = true;
            prev = maxp;
            maxp = -1;
            for ( j = 1; j < n; ++j ) 
                if ( !vis[v[j]] ) {
                    d[v[j]] += g[v[prev]][v[j]];
                    if ( maxp == -1 || d[v[maxp]] < d[v[j]] ) maxp = j;
                }
        }
    }
    return res;
}
            
int main()
{
    while ( scanf("%d%d", &n, &m ) == 2 ) {
        memset( g, 0, sizeof(g) );
        int x, y, z;
        while ( m-- ) {
            scanf("%d%d%d", &x, &y, &z);
            g[x][y] += z;
            g[y][x] += z;
        }
        printf("%d\n", Stoer_wagner());
    }
}

解题参考:http://blog.csdn.net/ac_lion/article/details/8866585