首页 > 代码库 > HDU 1565

HDU 1565

http://acm.hdu.edu.cn/showproblem.php?pid=1565

先进行二分图黑白染色,S到黑,白到T,黑到白,问题转化成了求最大权独立集,最大权独立集=sum-最小点权覆盖集,最小点权覆盖集等于上图最小割

#include <iostream> #include <cstdio>#include <cstring>using namespace std ;const int INF=0xfffffff ;struct node{    int s,t,cap,nxt ;}e[400005] ;int m,n,cnt,head[100005],level[100005],q[100005] ;void add(int s,int t,int cap){    e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;    e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap=0 ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;}bool build(int s,int t){    int front=0,rear=0 ;    memset(level,-1,sizeof(level)) ;    q[rear++]=s ;    level[s]=1 ;    while(front<rear)    {        int u=q[front++] ;        for(int i=head[u] ;i!=-1 ;i=e[i].nxt)        {            int tt=e[i].t ;            if(level[tt]==-1 && e[i].cap>0)            {                level[tt]=level[u]+1 ;                if(tt==t)return true ;                q[rear++]=tt ;            }        }    }    return false ;}int find(int s,int t,int flow){    if(s==t)return flow ;    int ret=0,a ;    for(int i=head[s] ;i!=-1 ;i=e[i].nxt)    {        int tt=e[i].t ;        if(level[tt]==level[s]+1 && e[i].cap>0)        {            a=find(tt,t,min(e[i].cap,flow-ret)) ;            e[i].cap-=a ;            e[i^1].cap+=a ;            ret+=a ;            if(ret==flow)                return ret ;        }    }    if(!ret)level[s]=-1 ;    return ret ;}int dinic(int s,int t){    int flow,ret=0 ;    while(build(s,t))        while(flow=find(s,t,INF))            ret+=flow ;    return ret ;}int Map[205][205] ;int main(){    int N ;    while(~scanf("%d",&N))    {        cnt=0 ;        memset(head,-1,sizeof(head)) ;        int S,T ;         int sum=0 ;        for(int i=1 ;i<=N ;i++)        {            for(int j=1 ;j<=N ;j++)            {                scanf("%d",&Map[i][j]) ;                sum+=Map[i][j] ;            }        }        S=0 ;T=N*N+1 ;        for(int i=1 ;i<=N ;i++)        {            for(int j=1 ;j<=N ;j++)            {                int num=(i-1)*N+j ;                if((i+j)&1)                {                    if(i>1)add(num,num-N,INF) ;                    if(i<N)add(num,num+N,INF) ;                    if(j>1)add(num,num-1,INF) ;                    if(j<N)add(num,num+1,INF) ;                    add(S,num,Map[i][j]) ;                }                else add(num,T,Map[i][j]) ;            }        }        printf("%d\n",sum-dinic(S,T)) ;    }    return 0 ;}
View Code