序
#define 嵬 为
怕自己忘记，写完这个 blog 就写作业，一群闲的蛋疼带科学家研究出的一个解决全局最小割的算法。
正文
算法思想：贪心
解决范畴： 对于一个无向图，每个边有割去的代价，问怎样割边能使这个图变为两个不连通的子图。
这个东西的名字叫做：全局最小割
咋做？反正我不理解，上课时 nk2005 也没有给证明，就发了个文章，让自己看，这哪会呀...
先给一个好实现的方法——利用网络瘤来解决
- 枚举源点和汇点
- 利用你会的各种网络瘤算法来搞出这个题比如说 ISAP, Dinic,
ek, HLPP（不会），反正谁闲的蛋疼写这个呀，又跑不过。。，据说拿 ISAP 用 LCT 维护时间复杂度可观？ - 然后跑出来最大流。。统计最优解
- 得出答案
我们看看时间复杂度？ 枚举源点和汇点，\(n^2\)， 一个网络瘤，少说时间复杂度 \(O(n^3)\) 然后，时间复杂度不低于 \(O(n^5)\) 图当作稠密图，即 \(m = n^2\)
反正，跑过去就是痴心妄想。
来说说 stoer-Wagner 算法，他的时间复杂度是 \(n - 1\) 次 \(prim\) 不加堆优化，加了堆（fib堆）优化之后可以优化到了 \(O(m + n \log n)\)，用优先队列（二叉堆）实现的话在稠密图无异于找死行为， 不妨把 \(m\) 看作是 \(n ^ 2\)，于是其实我们发现在稠密图上用朴素的 \(n^2\) prim 甚至可以得到最好的效果，常数小因为。（斐波那契堆不会写（大雾
先补充 \(prim\) 算法，找 \(n\) 个点的图的最大生成树，循环 \(n\) 次然后，每次找一个距离最大的点就 ok.于是一次 \(prim\) 的时间复杂度是 \(O(n^2)\)
其实这个算法的时间复杂度可以看成：
\[O(\sum _{i = 2} ^ {n} i^2 ) = O(\frac{n(n + 1)(2n + 1)}{6} - 1) = O(n^3) \]
在稀疏图上的算法不难自证罢。
开始说算法的步骤
- 首先随机找个点，做最大生成树，每一次把最后剩的两个点合并嵬一个点，最后的边权就是 \(min_cut\) 重复 \(n - 1\) 次直到最后省一个点。
stoer 算法基于下面的事实对于图中的任意两点 s, t 要么属于一个集合，要么分属于两个集合。如果是前者，我们在这一次最小割的计算就是最优解了，如果是后者，不难得到的是合并这两个点不影响答案。
记 \(W(i,j)\) 嵬 \(i->j\) 这个边的边权 \(c\) 这里的点指的是点集。
- 设最小割 \(min_cut=inf\), 任选一个点 ssinger
- 选出 ssinger 外一点集 p, 且 \(W(A,p)\) 最大的作为新的 \(s\), 若 \(A!=G(V)\), 则继续2.
- 把最后进入 \(A\) 的两点集记为 \(s\) 和 \(t\), 用 \(W(A,t)\) 更新 \(min_cut\).
- 合并点集 \(s,t\), 边权 \(w(u, v)=w(s, v)+w(t, v)\) , 删除顶点 \(s\) 和 \(t\), 以及与它们相连的边.
- 若 \(|V|!=1\) 则继续1.
如果你还不懂，附上学习资料
我们于是很开心的去实现代码，发现并不能很好的实现这个合并两个点集的操作，于是可以用并查集或者一些东西。进行操作。
并查集操作挺复杂的，对吧。
这是 hdu6801 的 AC 代码
#include <bits/stdc++.h>
#define gc() std::getchar()
#define pc(i) std::putchar(i)
template <typename T>
inline T read()
{
register T x = 0;
register char ch = gc();
register bool f = 0;
while(!std::isdigit(ch))
{
f = (ch == '-');
ch = gc();
}
while(std::isdigit(ch))
{
x = x * 10 + (ch - '0');
ch = gc();
}
return f ? -x : x;
}
template <typename T>
void put(T x)
{
if(x < 0)
{
x = -x;
pc('-');
}
if(x < 10) {
pc(x + 48);
return;
}
put(x / 10);
pc(x % 10 + 48);
return ;
}
#define Rep(i, j, k) for(int i = j; i >= k; --i)
#define vit std::vector <int>::iterator
#define sit std::string::iterator
#define vi std::vector <int>
#define lbd(i, j, k) std::lower_bound(i, j, k)
#define pii std::pair <int, int>
#define mkp(i, j) std::make_pair(i, j)
#define lowbit(i) (i & -i)
#define ispow(i) (!(i & (i - 1)))
#define rdi() read <int> ()
#define rdl() read <long long> ()
#define pti(i) put <int> (i), putchar('\n')
#define ptl(i) put <long long> (i), putchar(' ')
#define For(i, j, k) for(int i = j; i <= k; ++i)
#define pub(i) push_back(i)
#define pob() pop_back()
#define mm(i, j) memset(i, j, sizeof i)
#define F(i, j) for(int i = h[j]; ~i; i = edge[i].lac)
namespace RSX
{
const int Maxn = 3001;
int h[Maxn], cnt, mincut, n, m, dis[Maxn], link[Maxn], ssinger, f[Maxn];
bool vis[Maxn];
struct Edge
{
int to, lac, w;
inline void insert(int x, int y, int z) { to = y; lac = h[x]; h[x] = cnt++; w = z; }
}edge[Maxn * Maxn];
inline void add_edge(int z, int y, int x)
{
edge[cnt].insert(x, y, z);
edge[cnt].insert(y, x, z);
}
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
inline void merge(int x, int y)
{
int xx = x;
// 首先把这个链上的连上
while(~link[xx]) xx = link[xx];
link[xx] = y;
// merge 操作
f[y] = x;
}
int phase(int num, int &s, int &t)
{
// 做 prim
mm(dis, 0), mm(vis, 0);
std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int> >, std::less <std::pair <int, int> > > Q;
// duliu 的堆优化，轻易别写..
t = ssinger;
// 首先选这个点
while(--num)
{
// 找 num - 1 次
vis[s = t] = 1;
for(int u = s; ~u; u = link[u]) for(int i = h[u], to; ~i; i = edge[i].lac)
if(!vis[to = find(edge[i].to)]) Q.push(mkp(dis[to] += edge[i].w, to));
t = -1;
// 更新边权
while(!~t)
{
if(Q.empty()) return 0;
std::pair <int, int> tp = Q.top();
Q.pop();
// 就是说选这个是的点。但是好像也不用
if(dis[tp.second] == tp.first) t = tp.second;
}
// 找出最好的..
}
// 最后一次就是要的
return dis[t];
}
int store()
{
// 求最小割
mm(link, -1);
For(i, 1, n) f[i] = i;
// 初始化并查集
int res = 0x3f3f3f3f;
ssinger = rand() % n + 1;
for(int i = n, Singercoder, Tingercoder; i > 1; --i)
{
// 求每次的 min_cut
res = std::min(res, phase(i, Singercoder, Tingercoder));
if(res == 0) break;
// 合并两个并查集
merge(Singercoder, Tingercoder);
}
return res;
}
void fakemain()
{
while(~scanf("%d%d", &n, &m))
{
cnt = 0;
mm(h, -1);
For(i, 1, m) add_edge(rdi(), rdi() + 1, rdi() + 1);
pti(store());
}
return;
}
}
int main(int argc, char* argv[])
{
#ifdef _DEBUG
std::freopen("in.txt", "r", stdin);
#endif
RSX::fakemain();
return 0;
} 利用 bool 数组标记是否用过，然后进行合并边权。这是 poj2914 的 AC 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <bitset>
#include <algorithm>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#define gc() std::getchar()
#define pc(i) std::putchar(i)
template <typename T>
inline T read()
{
register T x = 0;
register char ch = gc();
register bool f = 0;
while(!std::isdigit(ch))
{
f = (ch == '-');
ch = gc();
}
while(std::isdigit(ch))
{
x = x * 10 + (ch - '0');
ch = gc();
}
return f ? -x : x;
}
template <typename T>
void put(T x)
{
if(x < 0)
{
x = -x;
pc('-');
}
if(x < 10) {
pc(x + 48);
return;
}
put(x / 10);
pc(x % 10 + 48);
return ;
}
#define Rep(i, j, k) for(int i = j; i >= k; --i)
#define vit std::vector <int>:: iterator
#define sit std::string:: iterator
#define vi std::vector <int>
#define lbd(i, j, k) std::lower_bound(i, j, k)
#define pii std::pair <int, int>
#define mkp(i, j) std::make_pair(i, j)
#define lowbit(i) (i & -i)
#define ispow(i) (!(i & (i - 1)))
#define rdi() read <int> ()
#define rdl() read <long long> ()
#define pti(i) put <int> (i), putchar('\n')
#define ptl(i) put <long long> (i), putchar(' ')
#define For(i, j, k) for(int i = j; i <= k; ++i)
#define pub(i) push_back(i)
#define pob() pop_back()
#define sst std::set <int>::iterator
namespace RSX
{
const int Maxn = 505, inf = 0x3f3f3f3f;
int mp[Maxn][Maxn], n, m, mincut, ssinger, dis[Maxn];
std::bitset <Maxn> flag, vis, null;
inline void add_edge(int z, int y, int x) { mp[x][y] = mp[y][x] += z; }
int stoer(int num, int &s, int &t)
{
vis &= null;
memset(dis, 0, sizeof dis);
dis[0] = -1;
while(num--)
{
int v = 0;
For(i, 1, n) if(!vis[i] && !flag[i] && dis[i] > dis[v]) v = i;
s = t;
vis[t = v] = 1;
For(i, 1, n) if(!vis[i] && !flag[i]) dis[i] += mp[t][i];
}
return dis[t];
}
void fakemain()
{
srand(20050217);
while(~scanf("%d%d", &n, &m))
{
ssinger = rand() % n + 1;
flag &= null;
memset(mp, 0, sizeof mp);
For(i, 1, m) add_edge(rdi(), rdi() + 1, rdi() + 1);
mincut = inf;
for(int i = n, Tingercoder, Singercoder; i > 1; --i)
{
int res = stoer(i, Singercoder, Tingercoder);
mincut = std::min(mincut, res);
flag[Tingercoder] = 1;
For(i, 1, n) if(!flag[i]) mp[i][Singercoder] = mp[Singercoder][i] += mp[Tingercoder][i];
mp[Singercoder][Singercoder] = 0;
}
pti(mincut);
}
return void();
}
}
int main(int argc, char* argv[])
{
#ifdef _DEBUG
std::freopen("in.txt", "r", stdin);
#endif
RSX::fakemain();
return 0;
} #undef 嵬
#define 嵬 尾
嵬
last article ： 单调队列 or AC_auto
京公网安备 11010502036488号