[Luogu] U18202 洞穴遇险

https://www.luogu.org/problemnew/show/U18202

暴力搜索预期得分3030分左右。

状压预期得分7070分左右。

考虑费用流，将剩余不稳定度和最小转为消除不稳定度和最大。

首先拐角处只能放在有不稳定度的格子上：如果它的拐角处放在了X+YX+Y为偶数的格子上，那么它不仅没有减少不稳定度，而且还占地。这个贪心显然正确。

那么黑白染色，X+YX+Y为偶数的点分一类，为奇数的分一类。将LL形柱子抽象成两个非拐角处的格子的路径（这两个格子的X+YX+Y都为偶数，拐角处的第三个格子的X+YX+Y为奇数）。那么这两个格子肯定一个在奇数列一个在偶数列，证明显然。

于是建图：

一共有四列点。
X+Y为偶数的点再分为两类：奇数列的和偶数列的。
奇数列的点放在左边（第一列），源点向每个点连一条容量为1，费用为0的边。
偶数列的点放在右边（第四列），每个点向汇点连一条容量为1，费用为0的边。
X+Y为奇数的点每个点拆开，一分为二，分别放在第二列和第三列。第二列的每个点向第三列的自己连一条容量为1，费用为负的该点的权值（不稳定度）。
如果第一列（X+Y为偶数，奇数列的点）和第二列的点相邻，连一条容量为1，费用为0的边，第三、四列同理。
当然塌了的格子不能连边。

跑一遍最小费用最大流即可。这样建图每次增广的流都肯定为11，所以可以在最大流为MM的时候直接跳出。期望得分4040分。

（？？？）

因为这样是错的，

就是一个构造的反例。我们不能先保证总流量最大再保证总费用最小，而是要尽可能地让总费用最小。也就是说我们要把柱子用在刀刃上，而不是放越多越好。于是想到如果本次增广源点到汇点的费用为正，直接跳出即可。（我的构造方式是连负费用边，如果连正权边跑最长路那么费用为负跳出即可）

彩蛋：

额，我不太会构造这样的数据，就把这一小片乘以1000贴在后面每个数据的左上角了。所以这么写也可以AC：printf("%d\n",sum+mincost-998000);

额我在说什么...

这样就可以100100分，复杂度O(O(费用流))。

题解：https://www.luogu.org/blog/zhoutb2333/dong-xue-yu-xian-ti-xie

暴力：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <string>

#include <ctime>

#include <cstdlib> 

using namespace std;

const int N = ;

#define yxy getchar()

#define R freopen("gg.in", "r", stdin)

bool vis[N][N];

int w[N][N];

int n, m, k, Answer, All;

inline int read(){

    int x = ; char c = yxy;

    while(c < '' || c > '') c = yxy;

    while(c >= '' && c <= '') x = x *  + c - '', c = yxy;

    return x;

}

void dfs(int step, int cut, int I, int J){

    if(cut > Answer) Answer = cut;

    if(step == m + ) return;

    for(int i = ; i <= n; i ++) {

        for(int j = ; j <= n; j ++){

            if(i < I && j < J) continue ;

            if(!vis[i][j] && w[i][j]){ //以当前点为拐点,每个点处枚举四种状态

                int x, y, x_, y_;

                x = i, y = j - , x_ = i - , y_ = j;

                if(y >  && x_ >  && !vis[x][y] && !vis[x_][y_]) { //朝向左上

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                    cut += w[i][j];

                    dfs(step + , cut, i, j);

                    cut -= w[i][j];

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                }

                x = i + , y = j, x_ = i, y_ = j + ;

                if(x <= n && y_ <= n && !vis[x][y] && !vis[x_][y_]) { //朝向右下

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                    cut += w[i][j];

                    dfs(step + , cut, i, j);

                    cut -= w[i][j];

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                }

                x = i, y = j - , x_ = i + , y_ = j;

                if(y >  && x_ <= n && !vis[x][y] && !vis[x_][y_]) { // 左下

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                    cut += w[i][j];

                    dfs(step + , cut, i, j);

                    cut -= w[i][j];

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                }

                x = i - , y = j, x_ = i, y_ = j + ;

                if(x >  && y_ <= n && !vis[x][y] && !vis[x_][y_]) { // 右上

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                    cut += w[i][j];

                    dfs(step + , cut, i, j);

                    cut -= w[i][j];

                    vis[i][j] = ; vis[x][y] = ; vis[x_][y_] = ;

                }

            }

        }

    }

}

int main()

{

    n = read(); m = read(); k = read();

    for(int i = ; i <= n; i ++)

        for(int j = ; j <= n; j ++){

            int W = read();

            w[i][j] = W, All += w[i][j];

        }

    for(int i = ; i <= k; i ++){

        int x = read(), y = read();

        vis[x][y] = ; //标记为1的已经塌陷

    }

    dfs(, , , );

    printf("%d", All - Answer);

    return ;

}

正解

#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=;

int pre[maxe],preedge[maxe],tmpflow[maxe],dis[maxe],s=,t=,E,ofs=;

int v[maxn][maxn],sum,n,m,k;

bool in[maxe];

queue<int> q;

int get(int x,int y,int lvl){

    return (x-)*n+y+ofs*lvl;

}

bool chk(int num){

    num%=ofs;

    int x=(num-)/n+,y=(num-)%n+;

    if(x<||y<||x>n||y>n||v[x][y]==-)

        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,,-c);

}

bool bfs(){

    memset(dis,0x3f,sizeof(dis));

    dis[s]=,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=;

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            scanf("%d",&v[i][j]),sum+=v[i][j];

    for(int i=;i<=k;i++)

        scanf("%d%d",&x,&y),v[x][y]=-;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            if((i+j)%)

                add(get(i,j,),get(i,j,),,-v[i][j]);

            else{

                if(j%){

                    add(s,get(i,j,),,);

                    add(get(i,j,),get(i,j-,),,);

                    add(get(i,j,),get(i,j+,),,);

                    add(get(i,j,),get(i-,j,),,);

                    add(get(i,j,),get(i+,j,),,);

                }

                else{

                    add(get(i,j,),t,,);

                    add(get(i,j-,),get(i,j,),,);

                    add(get(i,j+,),get(i,j,),,);

                    add(get(i-,j,),get(i,j,),,);

                    add(get(i+,j,),get(i,j,),,);

                }

            }

        }

    while(bfs()&&m){

        if(dis[t]>)

            break;

        int k=t;

        while(k!=s){

            flow[preedge[k]]-=tmpflow[t];

            flow[preedge[k]^]+=tmpflow[t];

            k=pre[k];

        }

        m-=tmpflow[t];

        mincost+=dis[t]*tmpflow[t];

    }

    printf("%d\n",sum+mincost);

    return ;

}

巴特西

[Luogu] U18202 洞穴遇险

最新文章

热门文章