方格取数问题

题目链接
给n*m的方格图,然后取数,要求取出来的数的位置不相邻,问最大值。
因为每个点只对他四周的点有影响,那么将点进行奇偶分隔,然后源点向奇点连边,偶点往汇点连边,然后奇点往周围的偶点连边,跑出最大流即最小割,即要扣去的代价,用总和减去即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 20000;
const ll maxm = 300000;
struct Edge{
	ll from, to, cap, flow;
	Edge(){
	}
	Edge(ll from, ll to, ll cap, ll flow):from(from), to(to), cap(cap), flow(flow){}	
};
struct Edge1
{
    ll from, to; ll dist;       
    Edge1(ll from, ll to, ll dist):from(from), to(to), dist(dist) {}
};
struct Dinic{
	ll n, m, s, t;
	vector<Edge>edges;
	vector<ll>G[MAXN];
	ll d[MAXN];
	ll cur[MAXN];
	ll vis[MAXN];
	void init(ll n, ll s, ll t)
	{
		this->n = n;this->s = s;this->t = t;
		edges.clear();
		for(ll i = 0;i <= n;++i) G[i].clear();
	}
	
	void add_edge(ll from, ll to, ll 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<ll>Q;
		Q.push(s);
		d[s] = 0;
		vis[s] = true;
		while(!Q.empty())
		{
			ll x = Q.front();
			Q.pop();
			for(ll i = 0;i < G[x].size();++i)
			{
				Edge& e = edges[G[x][i]];
				if(!vis[e.to] && e.cap > e.flow)
				{
					vis[e.to] = true;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}		
		}
		return vis[t];
	}
	ll dfs(ll x,ll a)
	{
		if(x == t || a == 0)return a;
		ll flow = 0, f;
		for(ll& 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;
	}
	ll maxflow()
	{
		ll flow = 0;
		while(bfs())
		{
			memset(cur, 0, sizeof(cur));
			flow += dfs(s,inf);
		}
		return flow;
	}
}gao;
int a[105][105];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int S=n*m+1;
	int T=n*m+2;
	gao.init(T,S,T);
	ll sum=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			sum+=a[i][j];
			if((i+j)%2==0){
				gao.add_edge(S,(i-1)*m+j,a[i][j]);
				for(int k=0;k<4;k++){
					int x=i+d[k][0];
					int y=j+d[k][1];
					if(x>0&&x<=n&&y>0&&y<=m){
						gao.add_edge((i-1)*m+j,(x-1)*m+y,inf);
					}
				}
			}else{
				gao.add_edge((i-1)*m+j,T,a[i][j]);
			}
		}
	}
	printf("%lld\n",sum-gao.maxflow());
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注