【P2774】方格取数问题（贪心+最大流，洛谷）

首先，我们要读懂这道题，否则你会和我一开始产生一样的疑问，把所有的数都取走剩下一个最小的不就可以了么？？？然后我们发现样例完全不是这么回事。题目中所说的使相邻的两个数没有公共边，是指你去走的数，也就是取完之后矩阵里的空白格子。明白了这一点，我们可能会有一个比较基础的贪心思想，没错，就是隔一个取一个，但是这么做并不可行，具体反例很容易找。然后我们通过观察，发现这道题和某最大权闭合子图有些类似，如果我们全取所有点，删去最小割说不准可行。
开始考虑建图，首先所有的奇数格子连源点，偶数格子连汇点，边权为点权。他们之间的边只连奇数到偶数的，边权为inf，这么连是为了避免重复计算。然后直接DINIC最大流就可以了。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define ll long long #define inf 50000000 #define re register #define id m*(i-1)+j using namespace std; struct po {int from,to,dis,nxt; }edge[1000001]; int head[1000001],cur[1000001],dep[60001],n,m,s,t,u,num=-1,x,y,l,tot,sum,d; int nm,a[120][120]; int dx[5]={0,1,0,-1,0}; int dy[5]={0,0,1,0,-1}; inline int read() {int x=0,c=1;char ch=' ';while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();while(ch=='-')c*=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();return x*c; } inline void add_edge(int from,int to,int dis) {edge[++num].nxt=head[from];edge[num].from=from;edge[num].to=to;edge[num].dis=dis;head[from]=num; } inline void add(int from,int to,int dis) {add_edge(from,to,dis);add_edge(to,from,0); } inline bool bfs() {memset(dep,0,sizeof(dep));queue<int> q;while(!q.empty())q.pop();dep[s]=1;q.push(s);while(!q.empty()){int now=q.front();q.pop();for(re int i=head[now];i!=-1;i=edge[i].nxt){int v=edge[i].to;if(dep[v]==0&&edge[i].dis>0){dep[v]=dep[now]+1;if(v==t)return 1;q.push(v); }}}return 0; } inline int dfs(int u,int dis) {if(u==t)return dis;int diss=0;for(re int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].to;if(dep[v]==dep[u]+1&&edge[i].dis!=0){int check=dfs(v,min(dis,edge[i].dis));if(check>0){diss+=check;dis-=check;edge[i].dis-=check;edge[i^1].dis+=check;if(dis==0) break;}}}return diss; } inline int dinic() {int ans=0;while(bfs()){for(re int i=0;i<=t;i++)cur[i]=head[i];while(int d=dfs(s,inf))ans+=d;}return ans; } int main() {memset(head,-1,sizeof(head));n=read();m=read();s=0;t=n*m+1;for(re int i=1;i<=n;i++)for(re int j=1;j<=m;j++)a[i][j]=read(),sum+=a[i][j];for(re int i=1;i<=n;i++)for(re int j=1;j<=m;j++){if((i+j)%2==0)add(s,id,a[i][j]);elseadd(id,t,a[i][j]);for(re int h=1;h<=4;h++){int lx=i+dx[h],ly=j+dy[h];if(lx>=1&&lx<=n&&ly>=1&&ly<=m)if((lx+ly)%2!=0)add(id,(lx-1)*m+ly,inf);}}cout<<sum-dinic(); }

 

转载于:https://www.cnblogs.com/victorique/p/8426683.html

总结

以上是生活随笔为你收集整理的【P2774】方格取数问题（贪心+最大流，洛谷）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。