C++ 解法, 执行用时: 286ms, 内存消耗: 1908K, 提交时间: 2021-06-28 19:04:22
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int n,m,s,t,cnt,flowans,costans,pt;
int to[26005], nxt[26005], head[26005], cur[26005], d[26005], val[26005],A[55][55],B[55][55];
int dis[25000],vis[25000],inc[25000],pre[25000],a[55][55];
bool Vis[25005];
const int INF=0x3f3f3f3f,INF1=0x3f3f3f3f3f3f3f3fLL;
void add(int u, int v, int w,int anow) {
// cout<<u<<" "<<v<<" "<<w<<" "<<anow<<endl;
to[++cnt] = v;
val[cnt] = w;
d[cnt] = anow;
nxt[cnt] = head[u];
head[u] = cnt;
to[++cnt]=u;
val[cnt]=0;
d[cnt]=-anow;
nxt[cnt]=head[v];
head[v]=cnt;
}
bool SPFA(){
queue<int>Q;
fill(dis,dis+pt+1,INF1);
memset(vis,0,sizeof vis);
memset(Vis,0,sizeof Vis);
Q.push(s);
inc[s]=INF1;
dis[s]=0,vis[s]=1;
Vis[s]=1;
while(!Q.empty()){
int u=Q.front();
Q.pop();
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
if(!val[i])continue;
int v=to[i];
Vis[v]=1;
if(dis[v]>dis[u]+d[i]){
dis[v]=dis[u]+d[i];
pre[v]=i;
inc[v]=min(inc[u],val[i]);
if(!vis[v])vis[v]=1,Q.push(v);
}
}
}
if(!Vis[t]||dis[t]>=0)return 0;
return 1;
}
void max_flow_min_cost(){
while(SPFA()){
flowans+=inc[t];
costans+=dis[t]*inc[t];
int x=t,i;
while(x!=s){
i=pre[x];
val[i]-=inc[t];
val[i^1]+=inc[t];
x=to[i^1];
}
}
}
char S[55][55];
int dx[5]={-1,1,0,0},dy[5]={0,0,-1,1};
signed main(){
int T;
cin>>T;
int xd=0;
while(T--){
memset(cur,0,sizeof cur);
memset(A,0,sizeof A);
memset(B,0,sizeof B);
memset(head,0,sizeof head);
memset(d,0,sizeof d);
memset(nxt,0,sizeof nxt);
flowans=costans=0;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%s",S[i]+1);
cnt=1;pt=0;
s=pt++,t=pt++;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
A[i][j]=pt++;
B[i][j]=pt++;
}
int mu=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(S[i][j]=='#'){
mu++;
add(A[i][j],B[i][j],1,-a[i][j]-INF);
}
if(S[i][j]=='.'){
add(A[i][j],B[i][j],1,-a[i][j]);
}
if((i+j)&1){
add(s,A[i][j],1,0);
for(int k=0;k<=3;k++){
int x=i+dx[k],y=j+dy[k];
if(x>=1&&x<=n&&y>=1&&y<=m){
add(B[i][j],A[x][y],1,0);
}
}
}else{
add(B[i][j],t,1,0);
}
}
}
max_flow_min_cost();
costans+=1ll*mu*INF;
if(abs(costans)>=1ll*n*m*1000){
cout<<"no solution"<<endl;
}else cout<<-costans<<endl;
}
return 0;
}
/*
1
3 3
...
..#
...
1000 1000 1000
-144 -999 152
442 71 -666
3
3 3
...
.*.
...
1 1 1
1 0 1
1 1 1
3 3
###
###
###
1 2 3
4 5 6
7 8 9
3 3
...
..#
...
10 8 6
12 1 -10
1 3 5
*/
的数据，max(n,m)<=10，保证这部分数据是随机生成的。
每个格子的权值绝对值小于等于1000。接下来输入n行m列的字符。表示可以任意选择覆盖或者不覆盖。
表示该位置不能被覆盖。
表示该位置必须被覆盖。