洛谷(方格取数问题)

链接：https://www.luogu.org/problemnew/show/P2774
思路：题目要求在n*m的棋盘中取一些数字，使得任意两数字没有临边并且要求总和最大。这是个经典的最大独立集覆盖，首先如果要满足上述条件，我们可以理解为任意两点间互相独立，也就是在原图上切去一些边使得图独立，又要求剩下的点权最大（在加边时边权等于点权），也就是切去的要最小，那就是最小割了，而又已知最小割等于最大流，所以建图跑一遍最大流，再用总和减去最大流就是答案。建图的话先将图染色成二分图，相邻点之间拉一条容量为INF的边（都从染色的0到1），然后从源点到所有染色为0点拉一条容量为该点权值的边（这样最后跑出来的最大流就是数字的总和），染色为1的点到汇点拉一条容量为该点权值的边，跑最大流即可。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int maxn = 110*110;
const int INF = 1e9;

int a[110][110];
int color[110][110];

struct edge{
    int from,to,cap,flow;
};

struct Dinic{
    int n,m,s,t;
    vector<edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n){
        this->n = n;
        edges.clear();
        for(int i=0;i<=n;i++)G[i].clear();
    }

    void addedge(int from,int to,int cap){
        edges.push_back(edge{from,to,cap,0});
        edges.push_back(edge{to,from,0,0});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                edge &e = edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t||a==0)return a;
        int flow = 0,f;
        for(int &i = cur[x];i<G[x].size();i++){
            edge &e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow -=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }

    int maxflow(int s,int t){
        this->s = s;
        this->t = t;
        int flow = 0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }
}solver;

int main(){
    int sum = 0;
    scanf("%d%d",&m,&n);
    solver.init(n*m+1);
    for(int i=0;i<m;i++){
        color[i][0] = i%2;
        for(int j=0;j<n;j++){
            if(j)color[i][j] = !color[i][j-1]; 
            scanf("%d",&a[i][j]);
            sum+=a[i][j];
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(color[i][j]==1){
                solver.addedge(i*n+j,n*m+1,a[i][j]);
                continue;
            }
            solver.addedge(n*m,i*n+j,a[i][j]);
            if(i-1>=0)solver.addedge(i*n+j,(i-1)*n+j,INF);
            if(i+1<m)solver.addedge(i*n+j,(i+1)*n+j,INF);
            if(j-1>=0)solver.addedge(i*n+j,i*n+j-1,INF);
            if(j+1<n)solver.addedge(i*n+j,i*n+j+1,INF);
        }
    }
    int res = solver.maxflow(n*m,n*m+1);
    printf("%d\n",sum-res);
    return 0;
}