luogu2774 方格取数问题

S1

懵逼的我仍然沉浸在被zyc坑了一波的悲痛中，根本无心做题好伐……
就当锻炼思维了吧(去他MD！)
可能是刚才用脑过度了，现在一点思路都没有，这不科学啊，整理一下思路……
对于一个点，我们可以选，我们也可以不选。我们可以看做，如果选择这个点，那么与它相邻的点就没有选择权，如果不选择这个点，那么与它相邻的点就有选择权，但是仍然可以不选。

S2 如何抉择？

这里对于如何多选一还是很懵逼的。我们知道，大多数情况下网络流的题都是需要多选一的，可是一般都不能用流量为1的方式来选择。这个时候GAY哥提供了一种思路，就是求最小割，然后用总的来减去最小割就行了。我们知道，最大流虽然叫做最大流，但是真正决定它的是最小的边权，所以它具有最小的性质，所以就等于最小割。
所以在我们要最大结果的时候，可以把最大流想象成最小割的一种实现方式，构造出一个最小割的图，然后跑最大流就行了，因为它的结果和最小割是一样的。
对于这个题，我们就可以进行棋盘染色，染成黑白格，然后源点连接黑格，边权为点权，汇点连接白格，边权为点权，黑格和互相矛盾的白格之间连inf。这样看就是最小割套路题了，割掉一些黑格，割掉一些白格，使得源点和汇点不相连接，也就是说不存在既选一黑又选一白的情况了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,k,cnt,head[100000],cur[100000],dis[100000],all,ans,tot,s=0,t=10001,a[101][101];
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
struct node
{
    int from,to,dis,num,next;
}ljb[100000];
ini read()
{
    char c;int r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    return r;
}
inv add_edge(int x,int y,int z)
{
    ljb[++cnt].from=x;
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    ljb[cnt].next=head[x];
    head[x]=cnt;
}
inv add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;	
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
inv md(int x,int y)
{
	for (rint i=1;i<=4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if (xx>0 && xx<=m && yy>0 && yy<=n)
		{
			int zz=(xx-1)*n+yy;
			add((x-1)*n+y,zz,big);
		}
	}
}
int main()
{
	m=read();n=read();
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=m;i++)
		for (rint j=1;j<=n;j++)
		{
			a[i][j]=read();
			all+=a[i][j]; 
			int x=(i-1)*n+j;
			if (i%2) 
			{
				if (j%2) add(s,x,a[i][j]),md(i,j);
				else add(x,t,a[i][j]);
			}
			else
			{
				if (j%2) add(x,t,a[i][j]);
				else add(s,x,a[i][j]),md(i,j);
			}
		}
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	printf("%d",all-ans);
}

总结

1. 先说一个细节：对于head和cnt的初始化一定不要忘了在所有add的前面。
2. 总结一下矛盾问题：即我们上面说的多选一。对于存在矛盾，必须进行选择的点，在建图的时候，我们有一种思路，就是把两种立场分别标记为源点和汇点，然后选边站，两种选择必须二选一的连接起来，我们之前有过一道类似的题，叫做善意的投票(详见网络流学习笔记)。
3. 也就是说，我们把一道网络流的题目转化为最小割，如果搞懂最小割割出来的集合是什么含义，就比较好理解了。以这道题为例，最小割割出来的集合，与源点相连接的就是要选的黑点和白点，以太空那道题为例，与源点相连的就是要选的实验和仪器。我们再看善意的投票，与源点相连的就是同意睡午觉的，与汇点相连的就是不同意的，所以我们要连双向边，因为可以为朋友反悔。