POJ2125 Destroying The Graph 二分图 + 最小点权覆盖 + 最小割

思路来源：http://blog.csdn.net/lenleaves/article/details/7873441

求最小点权覆盖，同样求一个最小割，但是要求出割去了那些边，

只要用最终的剩余网络进行一次遍历就可以了，比较简单。

建图：同样是一个二分图，左边的点代表去掉出边，

右边的点代表去掉入边（小心别弄混），左边去掉出边的点与源点相连，

容量为wi- 。

然后更据给出的弧进行连线，权值为INF

使用很好理解的EK算法：（360MS）

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <climits>

#include <cstring>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#define mm(a) memset((a),0,sizeof((a)))

#define ll long long

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = ;

queue <int> que;

int vis[MAXN], res[MAXN], pre[MAXN];

int n, m, map[MAXN][MAXN];

int src, des;

stack <int> ss;

bool bfs(int src, int des){

    int index;

    memset(pre, -, sizeof(pre));

    while(!que.empty()) que.pop();

    pre[src] = ;

    que.push(src);

    while(!que.empty()){

        index = que.front();

        que.pop();

        for(int i = src; i <= des; ++i){

            if(pre[i] == - && map[index][i] > ){

                pre[i] = index;

                if(i == des)    return true;

                que.push(i);

            }

        }

    }

    return false;

}

int MaxFlow(int src, int des){

    int i, maxflow = ;

    while(bfs(src, des)){

        int minflow = INF;

        for(i = des; i != src; i = pre[i])

            minflow = min(minflow, map[pre[i]][i]);

        for(i = des; i != src; i = pre[i]){

            map[pre[i]][i] -= minflow;

            map[i][pre[i]] += minflow;

        }

        maxflow += minflow;

    }

    return maxflow;

}

void init(){

    mm(map);mm(vis);

}

void dfs(int p){

    if(vis[p]) return ;

    vis[p] = true;

    for(int i = src; i < des; ++i)

        if(!vis[i] && map[p][i]) dfs(i);

}

void solve(){

    int i, x, y, ans = , temp;

    init();

    for(i = ; i <= n; ++i)

        scanf("%d",&map[n + i][n *  + ]);

    for(i = ; i <= n; ++i)

        scanf("%d",&map[][i]);

    for(i = ; i <= m; ++i){

        scanf("%d%d",&x,&y);

        map[x][y + n] = INF;

    }

    n = n << ;

    src = , des = n + ;

    ans = MaxFlow(src, des);

    dfs();

    printf("%d\n",ans);

    n = n >> ;

    for(i = ; i <= n; ++i){

        if(!vis[i])

            ss.push(i);

        if(vis[i + n])

            ss.push(i + n);

    }

    printf("%d\n",ss.size());

    while(!ss.empty()){

        temp = ss.top();

        ss.pop();

        if(temp <= n)   printf("%d -\n",temp);

        else    printf("%d +\n",temp - n);

    }

}

int main(){

    while(EOF != scanf("%d%d",&n,&m))    solve();

    return ;

}

使用SAP + GAP 优化：(79MS)

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <climits>

#include <cstring>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#define mm(a) memset((a),0,sizeof((a)))

#define ll long long

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = ;

int n, m, map[MAXN][MAXN], dis[MAXN], gap[MAXN];

int src, des;

bool vis[MAXN];

stack <int> ss;

void init(){

    mm(dis);mm(gap);mm(map);mm(vis);

}

int sap(int u,int flow){

    if(u == des) return flow;

    int ans = , i, t;

    for(i = ; i <= n + ; ++i)

        if(map[u][i] && dis[u] == dis[i] + ){

            t = sap(i, min(flow - ans, map[u][i]));

            map[u][i] -= t, map[i][u] += t,ans += t;

            if(ans == flow) return ans;

        }

    if(dis[src] >= n + ) return ans;

    if(!--gap[dis[u]]) dis[src] = n + ;

    ++gap[++dis[u]];

    return ans;

}

void dfs(int p){

    if(vis[p]) return ;

    vis[p] = true;

    for(int i = ; i < n + ; ++i)

        if(!vis[i] && map[p][i]) dfs(i);

}

void solve(){

    int i, x, y, ans = , temp;

    init();

    for(i = ; i <= n; ++i)

        scanf("%d",&map[n + i][n *  + ]);

    for(i = ; i <= n; ++i)

        scanf("%d",&map[][i]);

    for(i = ; i <= m; ++i){

        scanf("%d%d",&x,&y);

        map[x][y + n] = INF;

    }

    n = n << ;

    src = , des = n + ;

    for(gap[] = n + ; dis[src] < n + ; )

        ans += sap(src,INF);

    dfs();

    printf("%d\n",ans);

    n = n >> ;

    for(i = ; i <= n; ++i){

        if(!vis[i])

            ss.push(i);

        if(vis[i + n])

            ss.push(i + n);

    }

    printf("%d\n",ss.size());

    while(!ss.empty()){

        temp = ss.top();

        ss.pop();

        if(temp <= n)   printf("%d -\n",temp);

        else    printf("%d +\n",temp - n);

    }

}

int main(){

    while(scanf("%d%d",&n,&m)!=EOF)    solve();

    return ;

}

巴特西

POJ2125 Destroying The Graph 二分图 + 最小点权覆盖 + 最小割

最新文章

热门文章