UVA 11594 UVA11603(与hdu4700类似) 点对点的最小割 Gomory-Hu 和Gusfield算法学习

UVA 11594：Gusfield算法

题意： 给你n个点的容量网络图(n <= 100)， 求出两两之间的最大流(最小割)

算法概述： 原先所有点在一个集合， 每次任选一个集合进行处理， 在集合内任选2个点，求一次最小割s-t，然后用s-t割更新 被这个割所能切割的点对(点对为已经选过的所有点组合出的任意两点之间的点对)，直到所有集合中点的个数为1时结束。

code在下面

UVA 11603: Gomory-Hu算法

题意：n个点(n <= 200), 给你任意两点间的最大流(最小割)， 让你构造一个容量网络满足这个条件。

分析：我们只要构造一个解就可以了，解可以是一颗树， 因为当解成环时， 总可以去掉环上的一条边，然后把这条边的容量加到其它所有该环内的边上去(可以自己去验证一下)。那么问题就变为如何构造这样一棵树

算法概述：我们每次找出所有点对中没有选过的最小的最小割，然后加入树边，然后就可以递归成 分别构造用该树边连接的2个集合的一颗树(子问题)， 2个集合是用当前选的s-t割给割开来的。直到子集合的点数小于等于1的情况就结束。

为什么选最小的最小割：因为这样保证之后选的s-t割比之前的大，这样就不会把前面s-t割割断。

如何判不可能：1.当点数>= 2时不能分成2个集合

2.分别两个集合内找一点，存在这两点之间的最小割 大于 当前选的s-t割。

code在下面

UVA 11594：

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int inf = 1e9+7;int n;int cap[204][204];struct node {int u, v, c;};vector <node> ans;bool dfs(vector <int> v) {    int Min = inf, i, j, sz = v.size();    if(sz <= 1) return 1;    for(i = 0; i < sz; i++)        for(j = i+1; j < sz; j++)            if(cap[v[i]][v[j]] < Min)                Min = cap[v[i]][v[j]];    vector <int> l, r;    l.push_back(v[0]);    for(i = 1; i < sz; i++)        if(cap[v[0]][v[i]] > Min) l.push_back(v[i]);        else r.push_back(v[i]);    if(l.empty() || r.empty()) return 0;    for(i = 0; i < l.size(); i++)        for(j = 0; j < r.size(); j++)            if(cap[l[i]][r[j]] != Min) return 0;    if(Min > 0)ans.push_back(node{l[0], r[0], Min});    return dfs(l) && dfs(r);}int main() {    int i, j, cas, ca = 1;    scanf("%d", &cas);    while(cas--) {    scanf("%d", &n);        vector <int> v;        for(i = 0; i < n; i++) {            for(j = 0; j < n; j++)                scanf("%d", &cap[i][j]);        }        printf("Case #%d: ", ca++);        ans.clear();        for(i = 0; i < n; i++) v.push_back(i);        if(dfs(v)) {            printf("%d\n", ans.size());            for(i = 0; i < ans.size(); i++)            printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].c);        }        else puts("Impossible");    }    return 0;}