P2774 方格取数问题

题面

洛谷 P2774

题目描述

在一个有 $m*n$ 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。

输入格式

第 1 行有 2 个正整数 $m$ 和 $n$,分别表示棋盘的行数和列数。接下来的 $m$ 行,每行有 $n$ 个正整数,表示棋盘方格中的数。

输出格式

程序运行结束时,将取数的最大总和输出。

思路

把每个格子看做一个点,向相邻的四个格子连边。当前的格子和四周的格子互斥。要让每个格子不与相邻的格子同时选,就是切断它们之间的边。切断边数的最小值就是最小割。

不需要的边割掉后,剩下的就是答案。

把格子黑白相间染色,源点向每一个黑格(或白格)$i$ 连权值为 $a[i]$ 的边,每一个白格(或黑格)$i$ 向汇点连权值为 $a[i]$ 的边,每个黑格(或白格)向相邻的格子连权值为 $+ \infty$ 的边。

跑一遍 Dinic,得到最小割(最大流)为 $ans$,答案即为 $\sum_i\sum_ja\lbrack i\rbrack\lbrack j\rbrack-ans$。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    d[S]=0;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        v[now]=0;
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (d[j]>d[now]&&s[i]){
            	d[j]=d[now]+1;
            	if (!v[j]){
	            	q.push(j);
	            	v[j]=1;
				}
			}
        }
    }
    if (d[T]<1000000000){
    	return 1;
	}
    return 0;
}
int dfs(long long x,long long minn,long long T){
	if (x==T){
		return minn;
	}
	int tmp=0;
	for (int i=last[x];i;i=nextt[i]){
        int j=to[i];
        if (d[j]==d[x]+1&&s[i]){
			tmp=dfs(j,min(minn,s[i]),T);
			if (tmp){
	            s[i]-=tmp;
	            s[i^1]+=tmp;
	            return tmp;
			}
		}
    }
    return 0;
}
long long dinic(long long S,long long T){
	long long ans=0,tmp=0;
	while (bfs(S,T)){
		while (1){
			tmp=dfs(S,2147483647,T);
			if (!tmp){
				break;
			}
			ans+=tmp;
		}
	}
    return ans;
}
inline int calc(int x,int y){
	return (x-1)*m+y;
}
int main(){
    long long S=10005,T=10006;
    cin>>n>>m;
    int sum=0;
    int a[105][105];
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		cin>>a[i][j];
    		sum+=a[i][j];
    		if ((i+j)%2==1){
    			add(S,calc(i,j),a[i][j]);
    			add(calc(i,j),S,0);
			}
			if ((i+j)%2==0){
				add(calc(i,j),T,a[i][j]);
				add(T,calc(i,j),0);
			}
		}
	}
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		if ((i+j)%2==1){
    			if (i>1){
	    			add(calc(i,j),calc(i-1,j),19260817);
	    			add(calc(i-1,j),calc(i,j),0);
				}
    			if (i<n){
	    			add(calc(i,j),calc(i+1,j),19260817);
	    			add(calc(i+1,j),calc(i,j),0);
				}
    			if (j>1){
	    			add(calc(i,j),calc(i,j-1),19260817);
	    			add(calc(i,j-1),calc(i,j),0);
				}
    			if (j<m){
	    			add(calc(i,j),calc(i,j+1),19260817);
	    			add(calc(i,j+1),calc(i,j),0);
				}
			}
		}
	}
    bfs(S,T);
    cout<<sum-dinic(S,T);
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇