思路：设置两个源点，。s 连红色格子且上限为正无穷， 连白色格子且上限为 ，相邻格子双向两边上限为1。求此网络中的最小割。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=910;
const int maxm=1e4+10;
int level[maxn],n,m,c,x,y;
int head[maxn],cnt;
bool is[maxn];
bool in(int x,int y){
    return x>=0 && x<n && y>=0 && y<n;
}
int f(int x,int y){
    return x*n+y;
}
struct edge{int v,nex;ll w;}e[maxm];
void init(){
    cnt=0;
    memset(head,-1,sizeof head);
}
void add(int u,int v,ll w){
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nex=head[u];
    head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op){
    add(u,v,w);
    add(v,u,op?0:w);
}
bool bfs(int s,int t){
    queue<int>q;
    memset(level,0,sizeof level);
    level[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(x==t)return 1;
        for(int u=head[x];~u;u=e[u].nex){
            int v=e[u].v;ll w=e[u].w;
            if(!level[v]&&w){
                level[v]=level[x]+1;
                q.push(v);
            }
        }
    }
    return 0;
}
ll dfs(int u,ll maxf,int t){
    if(u==t)return maxf;
    ll ret=0;
    for(int i=head[u];~i;i=e[i].nex){
        int v=e[i].v;ll w=e[i].w;
        if(level[u]+1==level[v]&&w){
            ll MIN=min(maxf-ret,w);
            w=dfs(v,MIN,t);
            e[i].w-=w;
            e[i^1].w+=w;
            ret+=w;
            if(ret==maxf)break;
        }
    }
    if(!ret)level[u]=-1;
    return ret;
}
ll Dinic(int s,int t){
    ll ans=0;
    while(bfs(s,t))
    ans+=dfs(s,INF,t);
    return ans;
}
int main(){
    init();
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        is[f(x,y)]=1;
    }
    int S=n*n+1,T=S+1;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(is[f(i,j)]){
                add2(S,f(i,j),INF,0);
                if(i+1<n){
                    if(is[f(i+1,j)]){
                        add2(f(i,j),f(i+1,j),INF,0);
                    }
                    else{
                        add2(f(i,j),f(i+1,j),1,0);
                    }
                }
                if(j+1<n){
                    if(is[f(i,j+1)]){
                        add2(f(i,j),f(i,j+1),INF,0);
                    }
                    else{
                        add2(f(i,j),f(i,j+1),1,0);
                    }
                }
            }
            else{
                add2(f(i,j),T,c,0);
                if(i+1<n){
                    add2(f(i,j),f(i+1,j),1,0);
                }
                if(j+1<n){
                    add2(f(i,j),f(i,j+1),1,0);
                }
            }
        }
    }
    printf("%d\n",Dinic(S,T));
    return 0;
}