挑战程序竞赛系列(25):3.5最大权闭合图

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/75565373

挑战程序竞赛系列(25):3.5最大权闭合图

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

POJ 2987: Firing

思路可以参考博文:http://www.hankcs.com/program/algorithm/poj-2987-firing.html

这种最大权闭合图转最大流的思路着实巧妙,具体步骤如下:

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

当然证明可以参考:《算法合集之《最小割模型在信息学竞赛中的应用》.pdf》

用人类的语言描述下为什么是正确的吧,首先需要明确几个点,假设取1,则连带的有1,2,4,5都会被牵扯进来,所以{1,2,4,5}就形成了一个小群体,称为最大权闭合图,weight{1,2,4,5}就是该集合的权值,题目要求该值最大,比较容易理解。那么选择结点2会发生什么情况?最大权闭合图变为了{2,5},所以选取不同的结点,所导致的闭合图也会不同,因此有了求max weight的这道题。

思路:最大权闭合图等价于简单割(当然是转换成图N的情况下),或者可以这么理解,每个从源点s出发的简单割与最大权闭合图一一对应。

问题来了,简单割是什么?和之前最大流中的割集有什么关系?应该说简单割是割集的一种特殊情况,即此割集的流量不为正无穷的情况称为简单割。

你可以把集合{1,2,4,5,s}看成S,那么剩余的结点为T,而该割集的C[S,T]必然是一个非无穷的正值。

证明:想象一下,由最大权闭合图组成的点集U{s},必然不会存在从该点集出来的边指向其他顶点,所以S到T的容量不可能包含正无穷。(证毕)

那么该问题就变成了求最小简单割(即最大流的最小割算法),那为啥上述公式就是答案了呢?最大权=正权值之和-最小割权值?

巧妙在于从s出发的边都是连接正权值的顶点,而汇点则都是负权值顶点指向t,所以当我们用简单割包含闭合图时,必然S到T的流量一定由负权值组成,那么某些正权值怎么办呢?分两种情况:

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

那么最大权 = 所有正权值 - 简单割,就变成了选择顶点的正值之和 - 负权值的容量之和。(证毕)

这样就把每个顶点可选和不选的情况,统一到求解最小割集,即求解最大流,高明。

代码如下:(TLE)

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);
            }
        }
    }

嘿,JAVA代码怎么又TLE了,心累,改成C++能AC。c++代码参考博文:http://www.hankcs.com/program/algorithm/poj-2987-firing.html

POJ 2914: Minimum Cut

求无向图的最小割集,起初的想法是把无向图构造成有向图,接着遍历所有可能的源点和汇点,但发现这种时间复杂度相当高,于是得另辟蹊径了。

其实它是著名的stoer_wagner算法。。。好吧,又超出自己的能力范围学习起来痛苦万分。可以说它是一种符合某种情形下的遍历,又或者有点像松弛法,因为它的核心思想是,不断改进解,直到解不能再改变,或者说它的所有情况都被遍历完了,自然最后留下的便是最小割集。

来说说它的思路吧,这比较有趣,既然是不断改善解,那么我们自然就能想到遍历所有源点和汇点,找寻任意一对源点和汇点的最小割集,那它是全局的最小割集么?

不一定,假设全局的最小割集已知,那么上述任意的源点s和汇点t会出现两种情况:

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

第二点可以理解成,哪怕你找到了源点s和汇点t正好是全局的最小割集,我们依旧假设它们位于全局最小割集的某一部分S或者T,这样程序会继续执行,保证全局是最优的(自然某个时刻你找到的s和t是全局最小割集),那么是什么降低了时间复杂度?

合并,每次合并,意味着找寻最小割集的顶点都会少一个,而且我们不需要遍历所有可能的源点和汇点,而是从中找任意一个源点和汇点即可。

所以现在的问题是:给定一个无向图,如何找到一个源点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.

证明:采用反证法,假设存在存在两个候选的结点t1, t2,如果选择较小的W(A, t1)进入s,那么必然A与t2产生割集,而它们的边权之和等于W(A, t2) + W(t1, t2),不管t1和t2之间是否有边相连,选择t1产生的割集一定比选择t2产生的割集大,这就与假设矛盾,意味着必须选择较大的W(A, p)进入集合A。

代码如下:

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

翻译参考:http://www.hankcs.com/program/algorithm/poj-3155-hard-life.html

心机婊:公司内部共 n 个员工,员工之间可能两两合不来。若员工u 和员工 v 有矛盾,用边(u, v)表示,共 m 个矛盾。突然大股东送来一个富二代,威胁到你的CEO宝座。你想分配给富二代一个垃圾团队,使得团队成员间的不团结率最高。不团结率定义为团队人员间的矛盾总数与被裁人员数的比值(不团结率 = 团队人员之间的矛盾总数 / 团队人员数)。

好吧,此题是经典的求最大密度子图,所需要的知识点较多,覆盖了分数规划,二分法,以及最大流,最小割等知识点。

具体可以参考算法合集系列《算法合集之《最小割模型在信息学竞赛中的应用》.pdf》

此处说说一些思路,还是比较容易理解的,首先对该问题进行形式化,于是有了:

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}

于是就联想到了分数规划。。。接着就可以用二分了。。。好吧,说实话,我不知道怎么就能联想到分数规划了, 不过之前在leetcode刷题时,看到一些统一的模式,总结一下。它们都是求解极值问题,在所有符合子图性质情况下,求所有子图G′G'下的最大密度。所以,我们可以假定一个值g,有:

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

典型的分数规划模型,当h(g) < 0时,说明D < g,此时g太大,应该把g调小,而当h(g) > 0 时,说明D > g,此时需要调小g,直到g = d时,完成迭代。

说实在的,我们无非直接求出∑1⋅xe−∑g⋅xv=0\sum 1 \cdot x_e - \sum g \cdot x_v = 0的解,遇到的困难是我们无法得到最大密度子图G′G',所以我们只能利用二分,假定存在一个解,这样就能构造一个变形的图。

所以该问题就变成了max{h(g)},需要注意的是,为什么这里还存在一个max呢?因为构造h(g)的子图G′G'可以有多组,为了让所有的子图都小于等于D,必须让h(g)最大的满足h(g) = 0,此时的g才符合所有子图的最大的那个。

于是问题进一步转换成:

Maximize |E′|−g|V′|

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

此时《算法合集》中,利用了边的出度来计算V′V'下的边数,高明。但乍看一下,公式好像有点问题,个人觉得是:

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'}]

接着开始构造图G的转换图N,构造规则比较简单: 1. 新建源点s,和汇点t 2. s连接的顶点权值为u(图G的边数即可) 3. 所有顶点连接汇点的权值为u + 2g - dv 4. 其他顶点之间存在边则连接,权值为1

此时图N的最小割集算法就是上述的min目标函数,证明比较好理解,把图N分割成S和T,此时S到T的割集存在三部分,第一部分是原先的边权值为1的那些顶点,实际上求的是c[V′,V′^]c[V', \hat {V'}],第二部分是源点到所有在T中的顶点权值之和,为U|V′^|U\vert \hat{V'}\vert,第三部分是从S出发的顶点到汇点的权值之和,为U|V′|U\vert V'\vert.

所以整体代码如下:

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;
    }

不容易啊,居然过了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券