2013-team4/code/gomory-hu

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
给你任意两点间的最大流(最小割)， 让你构造一个容量网络满足这个条件。
首先这个容量网络肯定可以是一棵树，我们可以构造这棵树
我们每次找出所有点对中没有选过的最小的最小割，然后加入树边，然后就可以递归成分别构造用该树边连接的2个集合的一颗树(子问题)， 
2个集合是用当前选的s-t割给割开来的。直到子集合的点数小于等于1的情况就结束。
不可能条件：
1.当点数>= 2时不能分成2个集合
2.分别两个集合内找一点，存在这两点之间的最小割大于当前选的s-t割。
时间复杂度O(N^3)
}}}
{{{
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=200+10;
const int inf=1e9;

struct node {
    int u, v, w;
    node(){}
    node(int _u, int _v, int _w):u(_u), v(_v), w(_w){}
};

vector<node> ans;
int cap[MAXN][MAXN];
int n;

bool dfs(vector<int> &v) {
    int cut=inf, sz=v.size();
    if (sz<=1) return true;
    for (int i=0; i<sz; i++) 
        for (int j=i+1; j<sz; j++)
            if (cap[v[i]][v[j]]<cut) cut=cap[v[i]][v[j]];
    vector<int> left, right; left.clear(); right.clear();
    left.push_back(v[0]);
    for (int i=1; i<sz; i++)
        if (cap[v[0]][v[i]]>cut) left.push_back(v[i]);
        else right.push_back(v[i]);
    if (left.empty()||right.empty()) return false;
    for (int i=0; i<(int)left.size(); i++)
        for (int j=0; j<(int)right.size(); j++)
            if (cap[left[i]][right[j]]!=cut) return false;
    if (cut) ans.push_back(node(left[0], right[0], cut));
    return dfs(left)&&dfs(right);
}

int main() {
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        scanf("%d", &n);
        vector<int> v;
        for (int i=0; i<n; i++) 
            for (int j=0; j<n; j++)
                scanf("%d", &cap[i][j]);
        printf("Case #%d: ", cas);
        ans.clear();
        for (int i=0; i<n; i++) v.push_back(i);
        if (dfs(v)) {
            printf("%d\n", (int)ans.size());
            for (int i=0; i<(int)ans.size(); i++)
                printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].w);
        }
        else puts("Impossible");
    }
    return 0;
}
}}}

给你任意两点间的最大流(最小割)， 让你构造一个容量网络满足这个条件。
首先这个容量网络肯定可以是一棵树，我们可以构造这棵树
我们每次找出所有点对中没有选过的最小的最小割，然后加入树边，然后就可以递归成分别构造用该树边连接的2个集合的一颗树(子问题)， 
2个集合是用当前选的s-t割给割开来的。直到子集合的点数小于等于1的情况就结束。
不可能条件：
1.当点数>= 2时不能分成2个集合
2.分别两个集合内找一点，存在这两点之间的最小割大于当前选的s-t割。
时间复杂度O(N^3)

#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=200+10;
const int inf=1e9;
struct node {
    int u, v, w;
    node(){}
    node(int _u, int _v, int _w):u(_u), v(_v), w(_w){}
};
vector<node> ans;
int cap[MAXN][MAXN];
int n;
bool dfs(vector<int> &v) {
    int cut=inf, sz=v.size();
    if (sz<=1) return true;
    for (int i=0; i<sz; i++) 
        for (int j=i+1; j<sz; j++)
            if (cap[v[i]][v[j]]<cut) cut=cap[v[i]][v[j]];
    vector<int> left, right; left.clear(); right.clear();
    left.push_back(v[0]);
    for (int i=1; i<sz; i++)
        if (cap[v[0]][v[i]]>cut) left.push_back(v[i]);
        else right.push_back(v[i]);
    if (left.empty()||right.empty()) return false;
    for (int i=0; i<(int)left.size(); i++)
        for (int j=0; j<(int)right.size(); j++)
            if (cap[left[i]][right[j]]!=cut) return false;
    if (cut) ans.push_back(node(left[0], right[0], cut));
    return dfs(left)&&dfs(right);
}
int main() {
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; cas++) {
        scanf("%d", &n);
        vector<int> v;
        for (int i=0; i<n; i++) 
            for (int j=0; j<n; j++)
                scanf("%d", &cap[i][j]);
        printf("Case #%d: ", cas);
        ans.clear();
        for (int i=0; i<n; i++) v.push_back(i);
        if (dfs(v)) {
            printf("%d\n", (int)ans.size());
            for (int i=0; i<(int)ans.size(); i++)
                printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].w);
        }
        else puts("Impossible");
    }
    return 0;
}