题解：AT_abc407_g [ABC407G] Domino Covering SUM
include13_fAKe · · 题解
放在 ABC 的 G 的位置上的网络流题目里面最水的。估计是 ABC 用网络流题目作为压轴题的时代的落幕吧……
这题的 kenkoooo 分也比其他几题低了好几个档次。
首先对网格黑白染色，然后源向每一个黑格连流量为
流量为
#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 另外一种做法在于黑白格之间的连边费用为
#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 比赛中，也出现了很多优秀的网络流题。