[网络流24题] 方格取数问题/骑士共存问题 (最大流->最大权闭合图)

洛谷传送门 LOJ传送门

和太空飞行计划问题一样，这依然是一道最大权闭合图问题

“骑士共存问题”是“方格取数问题”的弱化版，本题解不再赘述“骑士共存问题”的做法

分析题目，如果我们能把所有方格的数都给取上，那么总和是一个定值$sum$

而题目要求我们取的数不能相邻，我们要想办法最大化$sum$取的数$-sum$没取的数

现在我们找到了一种取数方案，那么$sum$取的数一定能填补上$sum$没取的数，而且剩下的数总和$>0$，这样，方案才是有收益的

这不就是最大权闭合图的模型吗？

把每个格子拆成两个点，分别向源点和汇点连边，流量为它的权值，每个格子向四周连流量为$inf$的边

最小割割掉了用于填补的部分，用$sum-$最小割就是净收益了

方格取数问题：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define N1 2510
  6 #define M1 30100
  7 #define ll long long
  8 #define dd double
  9 #define inf 0x3f3f3f3f
 10 using namespace std;
 11 
 12 int gint()
 13 {
 14     int ret=0,fh=1;char c=getchar();
 15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 17     return ret*fh;
 18 }
 19 int n,m,nm,S,T;
 20 int p[N1],c[N1];
 21 int xx[]={-1,0,1,0},yy[]={0,1,0,-1};  
 22 struct Edge{
 23 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cte;
 24 void ae(int u,int v,int F)
 25 {
 26     cte++; to[cte]=v; flow[cte]=F;  
 27     nxt[cte]=head[u]; head[u]=cte;
 28 }
 29 }e;
 30 
 31 int que[M1],hd,tl,dep[N1],cur[N1];
 32 int bfs()
 33 {
 34     int x,j,v;
 35     memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
 36     hd=1,tl=0; que[++tl]=S; dep[S]=0; 
 37     while(hd<=tl)
 38     {
 39         x=que[hd++];
 40         for(j=e.head[x];j;j=e.nxt[j])
 41         {
 42             v=e.to[j]; 
 43             if(dep[v]==-1&&e.flow[j]>0)
 44                 dep[v]=dep[x]+1, que[++tl]=v;
 45         }
 46     }
 47     return dep[T]!=-1;
 48 }
 49 int dfs(int x,int limit)
 50 {
 51     int j,v,flow,ans=0; if(x==T||!limit) return limit;
 52     for(j=cur[x];j;j=e.nxt[j])
 53     {
 54         cur[x]=j; v=e.to[j];
 55         if( dep[v]==dep[x]+1 && (flow=dfs(v,min(e.flow[j],limit))) )
 56         {
 57             limit-=flow; ans+=flow;
 58             e.flow[j]-=flow; e.flow[j^1]+=flow;
 59             if(!limit) break;
 60         }
 61     }
 62     return ans;
 63 }
 64 int Dinic()
 65 {
 66     int mxflow=0;
 67     while(bfs())
 68         mxflow+=dfs(S,inf);
 69     return mxflow;
 70 }
 71 
 72 int a[N1];
 73 int check(int x,int y){ 
 74     if(x<1||y<1||x>n||y>m) return 0; return 1;}
 75 int id(int x,int y){ return (x-1)*m+y; }
 76 
 77 int main()
 78 {
 79     scanf("%d%d",&n,&m); nm=n*m; 
 80     int i,j,k,d,da,db,sum=0,ans; S=2*nm+1,T=2*nm+2; e.cte=1;
 81     for(i=1;i<=n;i++) for(j=1;j<=m;j++)
 82     {
 83         d=id(i,j); a[d]=gint(); sum+=a[d];
 84         e.ae(S,d,a[d]), e.ae(d,S,0);
 85         e.ae(d+nm,T,a[d]), e.ae(T,d+nm,0);
 86     }
 87     for(i=1;i<=n;i++) for(j=1;j<=m;j++)
 88     {
 89         da=id(i,j);
 90         for(k=0;k<4;k++) 
 91         if(check(i+xx[k],j+yy[k]))
 92         {
 93             db=id(i+xx[k],j+yy[k])+nm;
 94             e.ae(da,db,inf), e.ae(db,da,0);
 95         }
 96     }
 97     ans=sum-Dinic();
 98     printf("%d
",(sum-ans)/2+ans);
 99     return 0;
100 }

骑士共存问题：只需要把点权改成1 加几个特判就行了

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define L1 205
  6 #define N1 80050
  7 #define M1 400010
  8 #define ll long long
  9 #define dd double
 10 #define inf 0x3f3f3f3f
 11 using namespace std;
 12 
 13 int gint()
 14 {
 15     int ret=0,fh=1;char c=getchar();
 16     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 17     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 18     return ret*fh;
 19 }
 20 int n,m,nn,S,T;
 21 int p[N1],c[N1];
 22 int xx[]={-2,-1,1,2,2,1,-1,-2},yy[]={1,2,2,1,-1,-2,-2,-1};  
 23 struct Edge{
 24 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cte;
 25 void ae(int u,int v,int F)
 26 {
 27     cte++; to[cte]=v; flow[cte]=F;  
 28     nxt[cte]=head[u]; head[u]=cte;
 29 }
 30 }e;
 31 
 32 int que[N1],hd,tl,dep[N1],cur[N1];
 33 int bfs()
 34 {
 35     int x,j,v;
 36     memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
 37     hd=1,tl=0; que[++tl]=S; dep[S]=0; 
 38     while(hd<=tl)
 39     {
 40         x=que[hd++];
 41         for(j=e.head[x];j;j=e.nxt[j])
 42         {
 43             v=e.to[j]; 
 44             if(dep[v]==-1&&e.flow[j]>0)
 45                 dep[v]=dep[x]+1, que[++tl]=v;
 46         }
 47     }
 48     return dep[T]!=-1;
 49 }
 50 int dfs(int x,int limit)
 51 {
 52     int j,v,flow,ans=0; if(x==T||!limit) return limit;
 53     for(j=cur[x];j;j=e.nxt[j])
 54     {
 55         cur[x]=j; v=e.to[j];
 56         if( dep[v]==dep[x]+1 && (flow=dfs(v,min(e.flow[j],limit))) )
 57         {
 58             limit-=flow; ans+=flow;
 59             e.flow[j]-=flow; e.flow[j^1]+=flow;
 60             if(!limit) break;
 61         }
 62     }
 63     return ans;
 64 }
 65 int Dinic()
 66 {
 67     int mxflow=0;
 68     while(bfs())
 69         mxflow+=dfs(S,inf);
 70     return mxflow;
 71 }
 72 
 73 int mp[L1][L1];
 74 int check(int x,int y){ 
 75     if(x<1||y<1||x>n||y>n||mp[x][y]) return 0; return 1;}
 76 int id(int x,int y){ return (x-1)*n+y; }
 77 
 78 int main()
 79 {
 80     scanf("%d%d",&n,&m); nn=n*n; 
 81     int i,j,k,d,da,db,x,y,sum=0,ans; S=2*nn+1,T=2*nn+2; e.cte=1;
 82     for(i=1;i<=m;i++) x=gint(), y=gint(), mp[x][y]=1;
 83     for(i=1;i<=n;i++) for(j=1;j<=n;j++)
 84     {
 85         if(mp[i][j]) continue; d=id(i,j); sum++;
 86         e.ae(S,d,1), e.ae(d,S,0);
 87         e.ae(d+nn,T,1), e.ae(T,d+nn,0);
 88     }
 89     for(i=1;i<=n;i++) for(j=1;j<=n;j++)
 90     {
 91         if(mp[i][j]) continue; da=id(i,j); 
 92         for(k=0;k<8;k++) 
 93         if(check(i+xx[k],j+yy[k]))
 94         {
 95             db=id(i+xx[k],j+yy[k])+nn;
 96             e.ae(da,db,inf), e.ae(db,da,0);
 97         }
 98     }
 99     ans=sum-Dinic();
100     printf("%d
",(sum-ans)/2+ans);
101     return 0;
102 }