https://www.luogu.com.cn/problem/P2774
在一个有 m×n 个方格的棋盘中,每个方格中有一个正整数。
现要从方格中取数,使任意2个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。
输入格式:
文件第1行有2个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。
注意:m 是行数,n 是列数。
数据保证有 1≤n,m≤30
输出格式:
输出取数的最大总和。
输入样例:
在这里给出一组输入。例如:
3 3
1 2 3
3 2 3
2 3 1
``
输出样例:
在这里给出相应的输出。例如:11`
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+;
const int inf = 0x3f3f3f3f;
int n,m,s,t,tol,head[maxn],dep[maxn],x[][];struct Edge
{
int v,w,nxt;
}E[maxn];void add_edge(int u,int v,int w){
E[tol] = Edge{v,w,head[u]};
head[u] = tol++;
}void insert(int u, int v, int c){
add_edge(u, v, c);
add_edge(v, u, );
}bool Bfs(){
memset(dep,, sizeof(dep));
queue<int> q;
while(!q.empty())
q.pop();
q.push(s);
dep[s] = ;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u];i != -;i = E[i].nxt)
{
if(E[i].w && !dep[E[i].v])
{
dep[E[i].v] = dep[u] + ;
q.push(E[i].v);
if(E[i].v == t)
return true;
}
}
}
return false;
}int Dfs(int u,int f){
if(u == t)
return f;
int used = ,d = ;
for(int i = head[u];i != -;i = E[i].nxt){
if(dep[u] == dep[E[i].v] - && E[i].w){
if((d = Dfs(E[i].v,min(f - used,E[i].w)))){
used += d;
E[i].w -= d;
E[i^].w += d;
}
}
}
if(!used)
dep[u] = ;
return used;
}int Dinic(){
int max_flow = ,d;
while(Bfs()){
while((d = Dfs(s,inf)))
max_flow += d;
}
return max_flow;
}
signed main(){
//freopen(“in”,“r”,stdin);
ios::sync_with_stdio(false);
cin.tie();
memset(head,-, sizeof(head));
int ans = ,sz = ; cin >> m >> n;
s = ,t = m*n + ;
for(int i = ;i <= m; i++){
for(int j = ;j <= n; j++){
sz++;
cin >> x[i][j];
ans += x[i][j];
if((i+j)%){
insert(s,sz,x[i][j]);//连向源点
if(i > )
insert(sz,sz - n,inf);//把有限制条件的连起来,边权注意要尽量大
if(i < m)
insert(sz,sz + n,inf);
if(j > )
insert(sz,sz - ,inf);
if(j < n)
insert(sz,sz + ,inf); }
else
insert(sz,t,x[i][j]);//连向汇点
}
}
cout << ans - Dinic() << endl;//总的边权-最大流(最小割)
return ;
}