# 挑战程序竞赛系列（25）：3.5最大权闭合图

## POJ 2987: Firing

• 先构造网络流N，添加源点s，从s到正权值点做一条边，容量为点的权值。
• 添加汇点t，从负权值点到t做一条边，容量为点的权值的绝对值。
• 原来的边的容量统统设为无穷大。比如：
• 求解最小割，最大权=正权值之和-最小割权值
• 残余网络中的点的个数即为裁员个数。

• 正权值的顶点不在简单割集内，这种说明该顶点在可选和不可选中选择了不可选，所以s到该顶点必然有个正的分量，包含在简单割中。
• 正权值的顶点在简单割集内，这种说明该顶点在可选和不可选中选择了可选，所以简单割中不存在该容量。

static class Edge{
int from;
int to;
long cap;
int rev;
public Edge(int from, int to, long cap, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.rev = rev;
}
}

static long INF = 1 << 62;
static List<Edge>[] g;
static int V;
static int S;
static int T;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
V = N + 2;
S = 0;
T = N + 1;
count = 0;
visited = new boolean[V];
level = new int[V];
g = new ArrayList[V];
for (int i = 0; i < V; ++i){
g[i] = new ArrayList<Edge>();
}

long pos = 0;
for (int i = 0; i < N; ++i){
long cap = in.nextInt();
if (cap  > 0){
addEdge(S, i + 1, cap);
pos += cap;
}
else{
addEdge(i + 1, T, -cap);
}
}

for (int i = 0; i < M; ++i){
int from = in.nextInt();
int to = in.nextInt();
addEdge(from, to, INF);
}
long min = dinic();
solve(S);
System.out.println((--count) + " " + (pos - min));
}

public static void addEdge(int from, int to, long cap){
g[from].add(new Edge(from, to, cap, g[to].size()));
g[to].add(new Edge(to, from, 0, g[from].size() - 1));
}

static int[] level;
public static void bfs(int s){
for (int i = 0; i < V; ++i) level[i] = -1;
level[s] = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(s);
while (!queue.isEmpty()){
int v = queue.poll();
for (Edge e : g[v]){
int to = e.to;
if (level[to] < 0 && e.cap > 0){
level[to] = level[v] + 1;
queue.offer(to);
}
}
}
}

public static long dfs(int s, int t, long F, boolean[] visited){
if (s == t) return F;
visited[s] = true;
for (Edge e : g[s]){
int from = e.from;
int to = e.to;
if (!visited[to] && level[from] + 1 == level[to] && e.cap > 0){
long d = dfs(to, t, Math.min(F, e.cap), visited);
if (d > 0){
e.cap -= d;
g[to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}

public static long dinic(){
long flow = 0;
for (;;){
bfs(S);
if (level[T] < 0) break;
long f = 0;
while ((f = dfs(S, T, INF + 16, new boolean[V])) > 0) flow += f;
}
return flow;
}

static int count;
static boolean[] visited;
public static void solve(int s){
count ++;
visited[s] = true;
for (Edge e : g[s]){
int to = e.to;
if (e.cap > 0 && !visited[to]){
solve(to);
}
}
}

## POJ 2914: Minimum Cut

• 源点在最小割集的S部分，汇点在最小割集的T部分，此时你所遍历的源点和汇点的最小割集就是全局的最小割集，那么恭喜你，你很幸运一下子就找到了正确解。但如果不是呢？
• 另外一种情况是说源点和汇点都在全局最小割集的S部分或者T部分，那么显然你所找的关于s和t的最小割集一定不是最小的，但你会更新minCut，没关系，既然在全局最小割集的某一半部分，那么s和t合并之后再去求解最小割集是不会影响全局最小割集的。

stoer_wagner算法告诉我们： 1. 设最小割cut=INF, 任选一个点s到集合A中, 定义W(A, p)为A中的所有点到A外一点p的权总和. 2. 对刚才选定的s, 更新W(A,p)(该值递增). 3. 选出A外一点p, 且W(A,p)最大的作为新的s, 若A!=G(V), 则继续2. 4. 把最后进入A的两点记为s和t, 用W(A,t)更新cut. 5. 新建顶点u, 边权w(u, v)=w(s, v)+w(t, v), 删除顶点s和t, 以及与它们相连的边. 6. 若|V|!=1则继续1.

static int INF = 0x3f3f3f3f;
static int[][] g;
static int[] v;
static int[] w;
static int N;
static boolean[] visited;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
String[] nums = in.nextLine().trim().split(" ");
N = Integer.parseInt(nums[0]);
int M = Integer.parseInt(nums[1]);
g = new int[N][N];
v = new int[N];
for (int i = 0; i < M; ++i){
nums = in.nextLine().trim().split(" ");
int from = Integer.parseInt(nums[0]);
int to = Integer.parseInt(nums[1]);
int cap = Integer.parseInt(nums[2]);
g[from][to] += cap;
g[to][from] += cap;
}
System.out.println(stoerWagner(N));
}
in.close();
}

public static int stoerWagner(int n){
int minCut = INF;
for (int i = 0; i < n; ++i){
v[i] = i;
}

while (n > 1){
int pre = 0;
w = new int[N];
visited = new boolean[N];
for (int i = 1; i < n; ++i){
int k = -1;
for (int j = 1; j < n; ++j){ //求每次加入集合A之后的最大权值
if (!visited[v[j]]){
w[v[j]] += g[v[pre]][v[j]];
if (k == -1 || w[v[k]] < w[v[j]]){
k = j;
}
}
}
visited[v[k]] = true;
if (i == n - 1){
int s = v[pre], t = v[k];
minCut = Math.min(minCut, w[v[k]]); //更新最小割集
for (int j = 0; j < n; ++j){  //结点s和结点t合并
g[s][v[j]] += g[v[j]][t];
g[v[j]][s] += g[v[j]][t];
}
v[k] = v[--n]; //删除结点k
}
pre = k;
}
}
return minCut;
}

## POJ 3155: Hard Life

Maximize D=f(x)=∑e∈E1⋅xe∑v∈Vxv

Maximize \space D = f(x) = \frac{\sum_{e \in E} 1 \cdot x_e}{\sum_{v \in V} x_v}

D=f(x)=∑e∈E1⋅xe∑v∈Vxv=g

D = f(x) = \frac{\sum_{e \in E} 1 \cdot x_e}{\sum_{v \in V} x_v} = g

h(g)=∑1⋅xe−∑g⋅xv

h(g) = \sum 1 \cdot x_e - \sum g \cdot x_v

Maximize |E′|−g|V′|

Maximize \space \vert E'\vert - g \vert V'\vert

minimize g⋅|V′|−|E′|=∑v∈V′(2⋅g−dv)+c[V′,V′^]

minimize \space g \cdot \vert V'\vert - \vert E'\vert = \sum_{v \in V'} (2 \cdot g - d_v) + c[V', \hat {V'}]

class Pair{
int from;
int to;
public Pair(int from, int to){
this.from = from;
this.to = to;
}
}

double[][] graph;
Pair[] p;
int[] dv;
int N;
static final double esp = 1e-8;
void solve() {
N = ni();
int M = ni();
if (M == 0){
out.println("1");
out.println("1");
}
else{
dv = new int[N + 2];
graph = new double[N + 2][N + 2];

p = new Pair[M];
for (int i = 0; i < M; ++i){
int from = ni();
int to = ni();
dv[from] ++;
dv[to] ++;
p[i] = new Pair(from, to);
}

int s = 0, t = N + 1;
double lo = 1.0 / N;
double hi = M / 1.0;
double precision = 1.0 / N / N;
double hg = 0.0;
while (hi - lo >= precision){
double mid = (hi + lo) / 2.0;
constructGraph(mid, N, M);
hg = (N * M - dinic(0, N + 1)) / 2.0;
if (hg > esp) lo = mid;
else hi = mid;
}
constructGraph(lo, N, M);
dinic(s, t);
sum = 0;
boolean[] marked = new boolean[N + 2];
dfsTravel(s, marked);
out.println(sum - 1);
for (int i = 1; i <= N; ++i){
if (marked[i]){
out.println(i);
}
}
}
}

int sum;
public void dfsTravel(int v, boolean[] visited){
++sum;
visited[v] = true;
for (int j = 0; j < N + 2; ++j){
double cap = graph[v][j];
if (cap > 0.0 && !visited[j]){
dfsTravel(j, visited);
}
}
}

int[] level;
public void bfs(int s){
level = new int[N + 2];
Arrays.fill(level, -1);
level[s] = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(s);
while (!queue.isEmpty()){
int v = queue.poll();
for (int to = 0; to < N + 2; ++to){
double e = graph[v][to];
if (level[to] < 0 && e > 0){
level[to] = level[v] + 1;
queue.offer(to);
}
}
}
}

public double dfs(int s, int t, double f, boolean[] visited){
if (s == t) return f;
visited[s] = true;
for (int to = 0; to < N + 2; ++to){
double cap = graph[s][to];
if (!visited[to] && level[s] + 1 == level[to] && cap > 0){
double d = dfs(to, t, Math.min(f, cap), visited);
if (d > esp){
graph[s][to] -= d;
graph[to][s] += d;
return d;
}
}
}
return 0.0;
}

static final double INF = Double.MAX_VALUE;
public double dinic(int s, int t){
double flow = 0;
for (;;){
bfs(s);
if (level[t] < 0) break;
double f = 0;
while ((f = dfs(s, t, INF, new boolean[N + 2])) > 0) flow += f;
}
return flow;
}

public void constructGraph(double g, int N, int M){
graph = new double[N + 2][N + 2];

for (int i = 1; i <= N; ++i){ //s -> v
addEdge(0, i, M);
addEdge(i, N + 1, M + 2 * g - dv[i]);
}

for (Pair pair : p){
int from = pair.from;
int to = pair.to;
addEdge(from, to, 1);
addEdge(to, from, 1);
}
}

public void addEdge(int from, int to, double cap){
graph[from][to] += cap;
}

346 篇文章47 人订阅

0 条评论