列表

详情

NC220175. Chessboard

描述

Your are playing a computer game. The game is played on a chessboard of  rows and  columns.

For each grid on the board, you can choose to put a black piece or a white piece on it, or leave it blank. Denote  as the grid in the -th row and the -column. For each , putting a black piece on  earns you  points, while a white piece earns you  points, and leaving blank do not affect your score. The overall score will be the sum of the points earned by each piece. Note that a grid can contain at most one piece at the same time, that is, you cannot put a white piece and a black one simultaneously. It is guaranteed that ,  are all non-negative integers.

After you finish placing the pieces, the computer program checks whether the pieces are put in a \textbf{beautiful} way or not. Let's define  as the number of black pieces in the -th row,  as the number of black pieces in the -th column,  as the number of white pieces in the -th row, and  as the number of white pieces in the -th column. The pieces are considered \textbf{beautiful} if

Tired of high scores, you decide to minimize your score. To simplify the problem, you only need to output the minimum possible score among all beautiful placements of pieces.

输入描述

he first line of input contains two integers , denoting the number of rows and columns of the board.
The next  lines describe the points earned by putting black pieces. The -th of them contains  integers, the -th of which denotes .
The next  lines describe the points earned by putting white pieces. The -th of them contains  integers, the -th of which denotes .
The next  lines describe the constraints on each row, the -th of which contains two integers , whose meaning can be found in the statement above.
The next  lines describe the constraints on each column, the -th of which contains two integers , whose meaning can be found in the statement above.
It is guaranteed that there exists at least one strategy that satisfies all the constraints.

输出描述

Output a single integer, denoting the minimum score you can get.

示例1

输入: 

3 3
6 9 0
3 2 7
6 4 6
0 6 5
1 6 9
8 5 7
-3 -1
-3 0
1 3
0 0
1 1
-2 0

输出: 

9

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 59ms, 内存消耗: 736K, 提交时间: 2022-11-03 16:31:33 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int ec = 1,to[40005],nxt[40005],hed[205],cap[40005],w[40005],d[205];
void add_edge2(int f,int t,int c,int d){
	++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec; cap[ec] = c; w[ec] = d;
	++ ec; to[ec] = f; nxt[ec] = hed[t]; hed[t] = ec; cap[ec] = 0; w[ec] = -d;
}

void add_edge(int f,int t,int l,int r,int D){
	add_edge2(f,t,r - l,D);
	d[f] -= l; d[t] += l;
}

queue <int> q;
int inq[205],dis[205],flw[205],pre[205],prv[205];
bool spfa(int s,int t){
	for(int i = 0;i <= t;i ++){
		dis[i] = INF;
		inq[i] = 0;
		flw[i] = 0;
	}
	prv[t] = -1;
	q.push(s); inq[s] = 1; dis[s] = 0; flw[s] = INF;
	while(!q.empty()){
		int u = q.front(); q.pop();
		inq[u] = 0;
		for(int i = hed[u];i;i = nxt[i]){
			int v = to[i];
			if(dis[v] > dis[u] + w[i] && cap[i] > 0){
				dis[v] = dis[u] + w[i];
				prv[v] = u; pre[v] = i;
				flw[v] = min(flw[u],cap[i]);
				if(!inq[v]){
					inq[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return prv[t] != -1;
}

int mxf = 0,mcf = 0;
void mcmf(int s,int t){
	while(spfa(s,t)){
		mxf += flw[t];
		mcf += flw[t] * dis[t];
		int now = t;
		while(now != s){
			cap[pre[now]] -= flw[t];
			cap[pre[now] ^ 1] += flw[t];
			now = prv[now];
		}
	}
}

int n,m,sb[55][55],sw[55][55];

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	int S = n + m + 3,T = n + m + 4;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> sb[i][j];
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> sw[i][j];
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			add_edge(i,j + n,0,1,sb[i][j]);
			add_edge(i,j + n,1,1,0);
			add_edge(j + n,i,0,1,sw[i][j]);
		}
	}
	for(int i = 1;i <= n;i ++){
		int L,R; cin >> L >> R;
		add_edge(n + m + 1,i,L + m,R + m,0);
	}
	for(int j = 1;j <= m;j ++){
		int L,R; cin >> L >> R;
		add_edge(j + n,n + m + 2,L + n,R + n,0);
	}
	for(int i = 1;i <= n + m + 2;i ++){
		if(d[i] < 0) add_edge2(i,T,-d[i],0);
		if(d[i] > 0) add_edge2(S,i,d[i],0);
	}
	add_edge(n + m + 2,n + m + 1,0,INF,0);
	mcmf(S,T);
	cout << mcf << endl;
	return 0;
}

C++(clang++11) 解法, 执行用时: 19ms, 内存消耗: 560K, 提交时间: 2021-04-04 12:19:44 

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

typedef long long s64;
const int N=100+50,M=2e5+5;
struct Edge{
	int to,f,w,next;
}e[M];int ecnt=1,head[N];
void add_e(int x,int y,int f,int w){
	e[++ecnt]={y,f,w,head[x]};
	head[x]=ecnt;
	e[++ecnt]={x,0,-w,head[y]};
	head[y]=ecnt;
}
int S,T,TOT=0;
void add(int x,int f){
	if(f>0)add_e(S,x,f,0);
	else add_e(x,T,-f,0),TOT+=-f;
}

int f[N],g[N],fr[N];
bool in[N];
bool spfa(){
	for(int i=1;i<=T;++i){
		f[i]=0;
		g[i]=1e9;
	}
	f[S]=1e9;g[S]=0;
	deque<int>q;
	q.push_back(S);
	in[S]=1;
	while(!q.empty()){
		int x=q.front();q.pop_front();
		in[x]=0;
		for(int i=head[x];i;i=e[i].next)
		if(e[i].f && g[e[i].to]>g[x]+e[i].w){
			g[e[i].to]=g[x]+e[i].w;
			f[e[i].to]=min(f[x],e[i].f);
			fr[e[i].to]=i^1;
			if(!in[e[i].to]){
				q.push_back(e[i].to);
				in[e[i].to]=1;
			}
		}
	}
	return f[T]>0;
}

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j){
		int sb;
		scanf("%d",&sb);
		add_e(i,n+j,1,sb);
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j){
		int sw;
		scanf("%d",&sw);
		add_e(n+j,i,1,sw);
	}
	int s=n+m+1,t=s+1;S=t+1;T=S+1;
	add_e(t,s,1e9,0);
	add_e(s,t,1e9,0);
	int sum=0;
	for(int i=1;i<=n;++i){
		int l,r;
		scanf("%d%d",&l,&r);
		if (l>=0)
		{
			add(i,l);
			add_e(s,i,r-l,0);
			sum+=l;
		} else
		if (r<=0)
		{
			add(i,r);
			add_e(i,s,r-l,0);
			sum+=r;
		} else
		{
			add_e(s,i,r,0);
			add_e(i,s,-l,0);
		}
	}
	add(s,-sum);
	sum=0;
	for(int i=1;i<=m;++i){
		int l,r;
		scanf("%d%d",&l,&r);
		if (l>=0)
		{
			add(n+i,-l);
			add_e(n+i,t,r-l,0);
			sum+=l;
		} else
		if (r<=0)
		{
			add(i+n,-r);
			add_e(t,i+n,r-l,0);
			sum+=r;
		} else
		{
			add_e(i+n,t,r,0);
			add_e(t,i+n,-l,0);
		}
	}
	add(t,sum);
	
	int ans=0,tot=0;
	while(spfa()){
		int d=f[T];
		tot+=d;
		ans+=g[T]*d;
		for(int x=T;x!=S;){
			int i=fr[x];
			e[i].f+=d;e[i^1].f-=d; 
			x=e[i].to;
		}
	}
	cout<<ans<<endl;
}

上一题

© 2024 nowcoder.com