[bzoj4356][ceoi2014] wall

Description

題意太複雜了不想講

給你一個n*m的網格圖，有一些點是關鍵點，點（1，1）一定為關鍵點

每條邊有邊權

問用一個可以自交的環包住所有關鍵點的最小邊權和

n,m<=400

Solution

wxh修牆

可以發現對于每一個關鍵點，我們跑出從(1,1)到它左上角的最短路，可以證明最短路一定被包含在最優解中

那麼我們把每一個端點拆成左上左下右上右下4個點，跨過最短路的不連邊，把每個關鍵點四周的點給ban掉，然後跑1号點的右點到下點的最短路就是答案

證明畫個圖感受一下吧。。。。

Code

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
using namespace std;

typedef long long ll;
int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*+ch-'0';
    return x;
}

const int _N=,N=**,M=N*;

#define P(x,y) ((x-1)*(m+1)+y)
#define PP(x,y,z) ((P(x,y)-1)*4+z+1)

struct pty{
    int x;ll v;
    pty (int _x=,ll _v=) {x=_x;v=_v;}
    friend bool operator < (pty x,pty y) {
        return x.v<y.v;
    }
};
multiset<pty> s;

int lst[N],nxt[M],t[M],v[M],l;
void add(int x,int y,int z) {
    t[++l]=y;v[l]=z;nxt[l]=lst[x];lst[x]=l;
    t[++l]=x;v[l]=z;nxt[l]=lst[y];lst[y]=l;
}

bool bz[N];
void link(int x,int y,int z) {
    if (bz[x]||bz[y]) return;
    add(x,y,z);
}

ll dis[N];
int pre[N];
void dijkstra(int S) {
    s.clear();s.insert(pty(S,));
    memset(dis,,sizeof(dis));dis[S]=;
    while (!s.empty()) {
        pty now=*s.begin();
        int x=now.x;s.erase(s.begin());
        rep(i,x)
            if (dis[t[i]]>dis[x]+v[i]) {
                dis[t[i]]=dis[x]+v[i];pre[t[i]]=x;
                s.insert(pty(t[i],dis[t[i]]));
            }
    }
}

int n,m;

bool vis[N],mark[N][];
void find(int x) {
    if (x==||vis[x]) return;
    vis[x]=;
    if (pre[x]==x-) mark[x][]=mark[pre[x]][]=;
    if (pre[x]==x+) mark[x][]=mark[pre[x]][]=;
    if (pre[x]==x-m-) mark[x][]=mark[pre[x]][]=;
    if (pre[x]==x+m+) mark[x][]=mark[pre[x]][]=;
    find(pre[x]);
}

int cnt,X[N],Y[N],x,c[_N][_N],r[_N][_N];
void init() {
    n=read();m=read();
    fo(i,,n) fo(j,,m) {
        x=read();
        if (x==) ++cnt,X[cnt]=i,Y[cnt]=j;
    }
    fo(i,,n) fo(j,,m+) c[i][j]=read(),link(P(i,j),P(i+,j),c[i][j]);
    fo(i,,n+) fo(j,,m) r[i][j]=read(),link(P(i,j),P(i,j+),r[i][j]);
    dijkstra();
    fo(i,,cnt) find(P(X[i],Y[i]));
}

void solve() {
    fo(i,,cnt) bz[PP(X[i],Y[i],)]=bz[PP(X[i]+,Y[i],)]=bz[PP(X[i],Y[i]+,)]=bz[PP(X[i]+,Y[i]+,)]=;
    bz[]=;memset(lst,,sizeof(lst));l=;      
    fo(i,,n+)
        fo(j,,m+)
            fo(k,,) 
                if (!mark[P(i,j)][k]) 
                    link(PP(i,j,k),PP(i,j,(k+)%),);
    fo(i,,n) fo(j,,m+) link(PP(i,j,),PP(i+,j,),c[i][j]),link(PP(i,j,),PP(i+,j,),c[i][j]);
    fo(i,,n+) fo(j,,m) link(PP(i,j,),PP(i,j+,),r[i][j]),link(PP(i,j,),PP(i,j+,),r[i][j]);
    dijkstra();
    printf("%lld\n",dis[]);
}

int main() {
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    init();
    solve();
    return ;
}