不多说,先上一道题

原题目

Problem Description

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1876 Accepted Submission(s): 679

Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn’t give up. Caocao’s army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river, and based on those islands, Caocao’s army could easily attack Zhou Yu’s troop. Caocao also built bridges connecting islands. If all islands were connected by bridges, Caocao’s army could be deployed very conveniently among those islands. Zhou Yu couldn’t stand with that, so he wanted to destroy some Caocao’s bridges so one or more islands would be seperated from other islands. But Zhou Yu had only one bomb which was left by Zhuge Liang, so he could only destroy one bridge. Zhou Yu must send someone carrying the bomb to destroy the bridge. There might be guards on bridges. The soldier number of the bombing team couldn’t be less than the guard number of a bridge, or the mission would fail. Please figure out as least how many soldiers Zhou Yu have to sent to complete the island seperating mission.

Input There are no more than 12 test cases.

In each test case:

The first line contains two integers, N and M, meaning that there are N islands and M bridges. All the islands are numbered from 1 to N. ( 2 <= N <= 1000, 0 < M <= N2 )

Next M lines describes M bridges. Each line contains three integers U,V and W, meaning that there is a bridge connecting island U and island V, and there are W guards on that bridge. ( U ≠ V and 0 <= W <= 10,000 )

The input ends with N = 0 and M = 0.

Output For each test case, print the minimum soldier number Zhou Yu had to send to complete the mission. If Zhou Yu couldn’t succeed any way, print -1 instead.

Sample Input 3 3 1 2 7 2 3 4 3 1 4 3 2 1 2 7 2 3 4 0 0

Sample Output -1 4

题目意思

首先输入一个n和m, n表示几个顶点, m表示有几座桥。

然后要输入m行数据, 也就是这个桥具体的属性, 每一行包含三个数据, a, b, c, 分别表示桥的两端连的是哪两个点, 和这座桥上守卫的数量, 其实就是构建一个加权图而已..

嗯, 然后你要去炸桥..问你最少要派多少人去炸桥, 可以让这些点不变成连通图.

如果不能就输出-1

示例输入:

3   // 三个点, 三个桥

2 7 //  1号2号点之间有个桥, 桥上7个士兵

3 4 //  2号3号点之间有个桥, 桥上4个士兵

1 4 //  3号1号点之间有个桥, 桥上4个士兵
      
// 也就是对这个图来说..其实是个三阶完全图, 不管炸哪条都是强连通, 所以GG, 输出-1

2   // 三个点, 两个桥

2 7 // 1号2号之间连个桥, 7个士兵

3 4 // 2号3号之间连个桥, 4个士兵

// 也就是对这个图来说, 炸一个桥让他们不连通的话, 直接炸了那个4个士兵的桥就可以了, 所以输出应该是4

0 // 不管他.

示例输出

-1 4

思路

其实这题不是很难, 主要就是用tarjan算法求出可以炸哪些桥, 然后拿出一个最小值输出就行。

如果不熟悉或者不知道tarjan算法, 就GG咯

参考答案

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1010
#define INF 0x3f3f3f3
using namespace std;
struct Edge{
    int i, j, w;
}edge[max * (max - 1) / 2];

int all, node[max];
void addEdge(int i, int j, int w){
    edge[all].i = j;
    edge[all].w = w;
    edge[all].j = node[i];
    node[i] = all++;
    
    edge[all].i = i;
    edge[all].j = node[j];
    edge[all].w = w;
    node[j] = all++;
}

int n, m;
int i, j;
int dfn[max], low[max], sta[max], col[max];
int tt, sum, scc, top;

void tarjan(int u, int fa){
    dfn[u] = low[u] = ++tt;
    sta[++top] = u;
    for(i = node[u]; i; i = edge[i].j){
        int v = edge[i].i;
        if(!dfn[v]){
             sum++;
             tarjan(v, u);
             low[u] = min(low[u], low[v]);
        }else if(fa == v){
            if(cnt) low[u] = min(low[u], dfn[v]);
            cnt++;
        }else low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        int x;
        scc++;
        do{
            x = sta[top--];
            col[x] = scc;
        }while(x != u);
    }
}

int main(){
    int a, b, w;
    int ans;
    while(scanf("%d%d", &n, &m){
        if(n == 0 && m == 0) break;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(col, 0, sizeof(col));
        memset(head, 0, sizeof(head));
        all = sum = 1;
        tt = scc = top = 0;
        ans = 10010;
        while(m--){
            scanf("%d%d%d", &a, &b, &w);
            addEdge(a, b, w);
        }
        tarjan(1, 1);
        if(sum < n) puts("0");
        else{
            for(i = 1; i <= n; ++i){
                for(j = node[i]; j; j = edge[j].j){
                    int v = edge[j].i;
                    if(col[i] != col[v]) ans = min(ans, edge[j].w);
                }
            }
            printf("%d\n", ans ? (ans == 10010 ? -1 : ans) : 1);
        }
    }
    return 0;
}
        
    
        

什么是tarjan算法

用来求某个图强连通分量的算法, 如下图:

强连通分量为{1, 2, 3, 4}, {5}, {6};

算法思路就是dfs, 每个强连通分量就是搜索树中的一棵子树。搜索的时候，把当前搜索树点入栈, 回溯的时候就可以判断出来栈顶到栈中的结点是否为一个强连通分量.

这里有两个集合要用到, 一个是DNF[u]为结点u搜索的时间戳, 也就是次序编号, 还有一个Low[u]是结点u或者结点u的子树可以追溯到的最早的栈中结点的次序号.

一旦DNF[u] == LOW[u]的时候, 以u为根的搜索子树上所有结点是一个强连通分量.

下面是算法演示:

第一步

从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。

第二步

返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。

第三步

返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。

第四步

继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。

第五步

至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

每个点每条边都访问了一遍, 时间复杂度为O(N+M)。

参考c++代码

#define M 5010//题目中可能的最大点数
int STACK[M],top=0;//Tarjan算法中的栈
bool InStack[M];//检查是否在栈中
int DFN[M];//深度优先搜索访问次序
 
int Low[M];//能追溯到的最早的次序
int ComponentNumber=0;//有向图强连通分量个数
int Index=0;//索引号
vector<int> Edge[M];//邻接表表示
vector<int> Component[M];//获得强连通分量结果
int InComponent[M];//记录每个点在第几号强连通分量里
int ComponentDegree[M];//记录每个强连通分量的度
 
void Tarjan(int i)
{
    int j;
    DFN[i]=Low[i]=Index++;
    InStack[i]=true;STACK[++top]=i;
    for (int e=0;e<Edge[i].size();e++)
    {
        j=Edge[i][e];
        if (DFN[j]==-1)
        {
            Tarjan(j);
            Low[i]=min(Low[i],Low[j]);
        }
        else
            if (InStack[j]) Low[i]=min(Low[i],DFN[j]);
    }
    if (DFN[i]==Low[i])
    {
        ComponentNumber++;
        do{
            j=STACK[top--];
            InStack[j]=false;
            Component[ComponentNumber].
            push_back(j);
            InComponent[j]=ComponentNumber;
        }
        while (j!=i);
    }
}

参考资料:

L_Squirrel. 博客

tarjan算法百度百科