hdu 1569 &1565 (二分图带权最大独立集

要选出一些点,这些点之间没有相邻边且要求权值之和最大,求这个权值

分析:二分图带权最大独立集.

用最大流最小割定理求解.其建图思路是:将所有格点编号,奇数视作X部,偶数视作Y部,建立源点S和汇点T, S向X部的点建边,Y部向T建边,容量为该点权值.

相邻的一对点(肯定是一奇一偶),由X中的点向Y中的点建边,容量为正无穷.

最后跑出最大流,|带权最大独立集| = |点权之和| - |最小割| = |点权之和| - |最大流|

#include<iostream>

#include<cstring>

#include<stdio.h>

#include<algorithm>

#include<string>

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN=3010;//点数的最大值

const int MAXM=400010;//边数的最大值

#define captype int

struct SAP_MaxFlow{

    struct Edge{

        int from,to,next;

        captype cap;

    }edges[MAXM];

    int tot,head[MAXN];

    int gap[MAXN];

    int dis[MAXN];

    int cur[MAXN];

    int pre[MAXN];

    void init(){

        tot=0;

        memset(head,-1,sizeof(head));

    }

    void AddEdge(int u,int v,captype c,captype rc=0){

        edges[tot] = (Edge){u,v,head[u],c};  head[u]=tot++;

        edges[tot] = (Edge){v,u,head[v],rc}; head[v]=tot++;

    }

    captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意

        memset(gap,0,sizeof(gap));

        memset(dis,0,sizeof(dis));

        memcpy(cur,head,sizeof(head));

        pre[sNode] = -1;

        gap[0]=n;

        captype ans=0;

        int u=sNode;

        while(dis[sNode]<n){

            if(u==eNode){

                captype Min=INF ;

                int inser;

                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to])

                if(Min>edges[i].cap){

                    Min=edges[i].cap;

                    inser=i;

                }

                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to]){

                    edges[i].cap-=Min;

                    edges[i^1].cap+=Min;

                }

                ans+=Min;

                u=edges[inser^1].to;

                continue;

            }

            bool flag = false;

            int v;

            for(int i=cur[u]; i!=-1; i=edges[i].next){

                v=edges[i].to;

                if(edges[i].cap>0 && dis[u]==dis[v]+1){

                    flag=true;

                    cur[u]=pre[v]=i;

                    break;

                }

            }

            if(flag){

                u=v;

                continue;

            }

            int Mind= n;

            for(int i=head[u]; i!=-1; i=edges[i].next)

            if(edges[i].cap>0 && Mind>dis[edges[i].to]){

                Mind=dis[edges[i].to];

                cur[u]=i;

            }

            gap[dis[u]]--;

            if(gap[dis[u]]==0) return ans;

            dis[u]=Mind+1;

            gap[dis[u]]++;

            if(u!=sNode) u=edges[pre[u]^1].to;  //退一条边

        }

        return ans;

    }

}F;

int G[55][55];

int dir[4][2] = {1,0,-1,0,0,1,0,-1};

int main()

{

	#ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int N,M;

    int u,v,tmp;

    while(scanf("%d %d",&N, &M)==2){

        int S = 0,T = N*M+1;

        int sum  =0;

        F.init();

        for(int i=1;i<=N;++i){

            for(int j=1;j<=M;++j){

                scanf("%d",&tmp);

                G[i][j] = tmp;

                sum+=tmp;

            }

        }

        for(int i=1;i<=N;++i){

            for(int j=1;j<=M;++j){

                int id = (i-1)*M +j;

                if((i+j)&1){

                    F.AddEdge(S,id,G[i][j]);

                    for(int k=0;k<4;++k){

                        int nx = i+ dir[k][0];

                        int ny = j+ dir[k][1];

                        if(nx<1 || nx>N || ny<1 ||ny>M) continue;

                        int nid = (nx-1)*M + ny;

                        F.AddEdge(id,nid,INF);

                    }

                }

                else{

                    F.AddEdge((i-1)*M+j,T,G[i][j]);

                }

            }

        }

        int flow = F.maxFlow_sap(S,T,T+1);

        int res = sum - flow;

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

    }

    return 0;

}

巴特西

hdu 1569 &1565 (二分图带权最大独立集 - 最小割应用)

最新文章

热门文章