专栏文章

题解：AT_abc407_g [ABC407G] Domino Covering SUM

iinclude13_fAKe
AT_abc407_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioh3z6v
此快照首次捕获于
2025/12/02 19:06
3 个月前
此快照最后确认于
2025/12/02 19:06
3 个月前
查看原文
放在 ABC 的 G 的位置上的网络流题目里面最水的。估计是 ABC 用网络流题目作为压轴题的时代的落幕吧……
这题的 kenkoooo 分也比其他几题低了好几个档次。
首先对网格黑白染色，然后源向每一个黑格连流量为 11、费用为 00 的边，白格向汇连相同流量、费用的边。
流量为 11 代表每一个格子最多选 11 次。然后要连黑格向白格的边，只能在相邻的格子之间连。边权为两个格子的权值和。然后跑最小费用任意流即可（注意费用是可以为负数的）。
CPP
#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
int n,m,s=1,t=2,idx=2;	//这里的 idx 要和后面的区分开来  
int include13=0;	//先让答案等于所有的和 
int id[2025][2025];	//实际有用的不超过 1/1000 
int a[2025][2025]; 

int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct node{
	int to,nxt,w,x;
}edge[5*114514];
int head[2025];
int idx1=1;	//idx1 是边的数目  
void add(int u,int v,int w,int x){
	idx1++,edge[idx1]=(node){v,head[u],w,x},head[u]=idx1;
}
void Add(int u,int v,int w,int x){
//	cout<<"Add "<<u<<' '<<v<<' '<<w<<' '<<x<<endl;
	add(u,v,w,x),add(v,u,0,-x);
}

int zdl[2025];	//跑 SPFA 
int lst[2025],lst1[2025];	//代表双重作用 
int bfs(){
	queue<int> q;
	for(int i=1;i<=idx;i++){
		zdl[i]=lst[i]=lst1[i]=1e18;
	}
	zdl[1]=0;
	q.push(1);
	while(!q.empty()){
		//首先试一下不判断负环的做法 
		int u=q.front(); 
//		cout<<'#'<<u<<endl;
		q.pop();
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to,w=edge[i].w,x=edge[i].x;
			if(!w)	continue;	//走这样的地方没有意义 
			if(zdl[v]>zdl[u]+x){
				zdl[v]=zdl[u]+x;
//				cout<<'#'<<v<<' '<<u<<endl;
				lst[v]=u;
				lst1[v]=i; 
				if(v==1||v==2)	continue;	//故事并没有这么等来 只是为了防止到了终点还在往回走  
				q.push(v); 
//				cout<<'#'<<v<<endl;
			} 
		}
	}
//	for(int i=1;i<=idx-1;i++){
//		cout<<zdl[i]<<',';
//	}
//	cout<<zdl[idx]<<endl;
	return zdl[2]<=1e17;
} 
void solve(){
	while(bfs()){
		if(zdl[2]>=0)	break;	//其实已经没了  
		int now=2;
		int flow=1e18;	//flow 专门留到现在计算  
		while(now!=1){
			int lst_=lst[now],lst_1=lst1[now];
			flow=min(flow,edge[lst_1].w); 
			now=lst_;
		}
		now=2;
//		cout<<'#';
		while(now!=1){
//			cout<<now<<' ';
			int lst_=lst[now],lst_1=lst1[now];
			edge[lst_1].w-=flow,edge[lst_1^1].w+=flow;
			now=lst_;
		}
//		cout<<endl;
		include13-=zdl[2]*flow;
	}
	write2(include13);
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=read(),include13+=a[i][j],id[i][j]=++idx;
		}
	}
//	cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((i+j)%2==0){
				//代表第一层 
				Add(1,id[i][j],1,0);
				for(int k=0;k<4;k++){
					int x=i+dx[k],y=j+dy[k];
					if(1<=x&&x<=n&&1<=y&&y<=m){
						Add(id[i][j],id[x][y],1,a[i][j]+a[x][y]);
					}
				} 
			}
			else{
				Add(id[i][j],2,1,0);
			}
		}
	} 
//	cout<<endl;
	solve();
	return 0;
}//ABC407G
另外一种做法在于黑白格之间的连边费用为 00，而源边、汇边有费用。效果是完全相同的。
CPP
#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
int n,m,s=1,t=2,idx=2;	//这里的 idx 要和后面的区分开来  
int include13=0;	//先让答案等于所有的和 
int id[2025][2025];	//实际有用的不超过 1/1000 
int a[2025][2025]; 

int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct node{
	int to,nxt,w,x;
}edge[5*114514];
int head[2025];
int idx1=1;	//idx1 是边的数目  
void add(int u,int v,int w,int x){
	idx1++,edge[idx1]=(node){v,head[u],w,x},head[u]=idx1;
}
void Add(int u,int v,int w,int x){
//	cout<<"Add "<<u<<' '<<v<<' '<<w<<' '<<x<<endl;
	add(u,v,w,x),add(v,u,0,-x);
}

int zdl[2025];	//跑 SPFA 
int lst[2025],lst1[2025];	//代表双重作用 
int bfs(){
	queue<int> q;
	for(int i=1;i<=idx;i++){
		zdl[i]=lst[i]=lst1[i]=1e18;
	}
	zdl[1]=0;
	q.push(1);
	while(!q.empty()){
		//首先试一下不判断负环的做法 
		int u=q.front(); 
//		cout<<'#'<<u<<endl;
		q.pop();
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to,w=edge[i].w,x=edge[i].x;
			if(!w)	continue;	//走这样的地方没有意义 
			if(zdl[v]>zdl[u]+x){
				zdl[v]=zdl[u]+x;
//				cout<<'#'<<v<<' '<<u<<endl;
				lst[v]=u;
				lst1[v]=i; 
				if(v==1||v==2)	continue;	//故事并没有这么等来 只是为了防止到了终点还在往回走  
				q.push(v); 
//				cout<<'#'<<v<<endl;
			} 
		}
	}
//	for(int i=1;i<=idx-1;i++){
//		cout<<zdl[i]<<',';
//	}
//	cout<<zdl[idx]<<endl;
	return zdl[2]<=1e17;
} 
void solve(){
	while(bfs()){
		if(zdl[2]>=0)	break;	//其实已经没了  
		int now=2;
		int flow=1e18;	//flow 专门留到现在计算  
		while(now!=1){
			int lst_=lst[now],lst_1=lst1[now];
			flow=min(flow,edge[lst_1].w); 
			now=lst_;
		}
		now=2;
//		cout<<'#';
		while(now!=1){
//			cout<<now<<' ';
			int lst_=lst[now],lst_1=lst1[now];
			edge[lst_1].w-=flow,edge[lst_1^1].w+=flow;
			now=lst_;
		}
//		cout<<endl;
		include13-=zdl[2]*flow;
	}
	write2(include13);
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=read(),include13+=a[i][j],id[i][j]=++idx;
		}
	}
//	cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((i+j)%2==0){
				//代表第一层 
				Add(1,id[i][j],1,a[i][j]);
				for(int k=0;k<4;k++){
					int x=i+dx[k],y=j+dy[k];
					if(1<=x&&x<=n&&1<=y&&y<=m){
						Add(id[i][j],id[x][y],1,0);
					}
				} 
			}
			else{
				Add(id[i][j],2,1,a[i][j]);
			}
		}
	} 
//	cout<<endl;
	solve();
	return 0;
}//ABC407G

感言

网络流是一种非常优秀的算法，可以解决很多单纯最短路、SCC、DCC 不能解决的问题。
在历届 AtCoder 比赛中，也出现了很多优秀的网络流题。
2021∼20222021\sim 2022 赛季也是一个网络流题目迭出的赛季，学术社区和二次整数规划问题都是优秀的网络流题目。
但怎么网络流题目如今逐渐走向末路了？还是有些感伤的。
希望下一个登上压轴题舞台的算法不要落幕得太快。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...