洞穴遇险 题解

暴力搜索预期得分$30$分左右。 状压预期得分$70$分左右。 考虑费用流，将剩余不稳定度和最小转为消除不稳定度和最大。 首先**拐角处只能放在有不稳定度的格子上**：如果它的拐角处放在了$X+Y$为偶数的格子上，那么它不仅没有减少不稳定度，而且还占地。这个贪心显然正确。 那么黑白染色，$X+Y$为偶数的点分一类，为奇数的分一类。将$L$形柱子抽象成两个非拐角处的格子的路径（这两个格子的$X+Y$都为偶数，拐角处的第三个格子的$X+Y$为奇数）。**那么这两个格子肯定一个在奇数列一个在偶数列**，证明显然。 于是建图： - 一共有四列点。 - X+Y为偶数的点再分为两类：奇数列的和偶数列的。 - 奇数列的点放在左边（第一列），源点向每个点连一条容量为1，费用为0的边。 - 偶数列的点放在右边（第四列），每个点向汇点连一条容量为1，费用为0的边。 - X+Y为奇数的点每个点拆开，一分为二，分别放在第二列和第三列。第二列的每个点向第三列的自己连一条容量为1，费用为负的该点的权值（不稳定度）。 - 如果第一列（X+Y为偶数，奇数列的点）和第二列的点相邻，连一条容量为1，费用为0的边，第三、四列同理。 - 当然塌了的格子不能连边。 跑一遍最小费用最大流即可。这样建图每次增广的流都肯定为$1$，所以可以在最大流为$M$的时候直接跳出。期望得分$40$分。 （？？？） 因为这样是错的， ``` plain 4 4 6 0 1 0 1000 0 0 0 0 0 1 0 1 0 0 0 0 1 1 2 1 2 3 4 1 4 3 4 4 ``` 就是一个构造的反例。**我们不能先保证总流量最大再保证总费用最小，而是要尽可能地让总费用最小。也就是说我们要把柱子用在刀刃上，而不是放越多越好**。于是想到如果本次增广源点到汇点的费用为正，直接跳出即可。（我的构造方式是连负费用边，如果连正权边跑最长路那么费用为负跳出即可） **彩蛋：** 额，我不太会构造这样的数据，就把这一小片乘以1000贴在后面每个数据的左上角了。所以这么写也可以AC：printf("%d\n",sum+mincost-998000); 额我在说什么... 这样就可以$100$分，复杂度$O($费用流$)$。 ``` cpp #include<bits/stdc++.h> #define maxn 105 #define maxe 100010 #define INF 1<<30 using namespace std; int head[maxe],nxt[maxe],point[maxe],flow[maxe],val[maxe],tot=1; int pre[maxe],preedge[maxe],tmpflow[maxe],dis[maxe],s=0,t=100000,E,ofs=25000; int v[maxn][maxn],sum,n,m,k; bool in[maxe]; queue<int> q; int get(int x,int y,int lvl){ return (x-1)*n+y+ofs*lvl; } bool chk(int num){ num%=ofs; int x=(num-1)/n+1,y=(num-1)%n+1; if(x<1||y<1||x>n||y>n||v[x][y]==-1) return false; return true; } void ADD(int x,int y,int f,int c){ val[++tot]=c; flow[tot]=f; point[tot]=y; nxt[tot]=head[x]; head[x]=tot; } void add(int x,int y,int f,int c){ if((x!=s&&x!=t&&!chk(x))||(y!=s&&y!=t&&!chk(y))) return; ADD(x,y,f,c),ADD(y,x,0,-c); } bool bfs(){ memset(dis,0x3f,sizeof(dis)); dis[s]=0,in[s]=true,q.push(s),tmpflow[s]=m; while(!q.empty()){ int x=q.front(); in[x]=false; q.pop(); for(int j=head[x];j;j=nxt[j]){ if(!flow[j]||dis[point[j]]<=dis[x]+val[j]) continue; dis[point[j]]=dis[x]+val[j]; pre[point[j]]=x; preedge[point[j]]=j; tmpflow[point[j]]=min(tmpflow[x],flow[j]); if(!in[point[j]]) in[point[j]]=true,q.push(point[j]); } } return dis[t]!=0x3f3f3f3f; } int main(){ int x,y,mincost=0; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&v[i][j]),sum+=v[i][j]; for(int i=1;i<=k;i++) scanf("%d%d",&x,&y),v[x][y]=-1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if((i+j)%2) add(get(i,j,1),get(i,j,2),1,-v[i][j]); else{ if(j%2){ add(s,get(i,j,0),1,0); add(get(i,j,0),get(i,j-1,1),1,0); add(get(i,j,0),get(i,j+1,1),1,0); add(get(i,j,0),get(i-1,j,1),1,0); add(get(i,j,0),get(i+1,j,1),1,0); } else{ add(get(i,j,3),t,1,0); add(get(i,j-1,2),get(i,j,3),1,0); add(get(i,j+1,2),get(i,j,3),1,0); add(get(i-1,j,2),get(i,j,3),1,0); add(get(i+1,j,2),get(i,j,3),1,0); } } } while(bfs()&&m){ if(dis[t]>0) break; int k=t; while(k!=s){ flow[preedge[k]]-=tmpflow[t]; flow[preedge[k]^1]+=tmpflow[t]; k=pre[k]; } m-=tmpflow[t]; mincost+=dis[t]*tmpflow[t]; } printf("%d\n",sum+mincost); return 0; } ```