首页 > 代码库 > 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 ;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。