题解 P3956 【棋盘】

2017-11-16 21:05:15


_一个提高D1T2莫名炸了的蒟蒻写写普及_

不会打删除线

其实当我发这份题解的时候发现楼下有更妙的做法,但是如果加入了下面的思想似乎会更快。

建图部分是每个点拆成两种颜色,采用异色1同色0,空白点出边同色0异色1,入边同色2异色3

显然每个点出发最多会有无向边4对(上下左右),然后点数10000个,于是总边数(无向边算一条)会有40000+条。于是我们考虑传统最短路:发现它的复杂度中总是要带个m(边数),于是我们很不愉快,于是我们考虑bfs。

重要部分:

显然bfs每个点只需要走一遍,而且终点只会被更新一次,所以我们可以比其他算法提前结束。但是我们的边权不是1如何?

对于大于1的将一条边拆成K个点,k=边权-1,然后每条边权为1

对于边权为0的边,显然相当于u可以直达v,但是如果我把v入队然后v的出边比其它点更晚更新v的出边怎么办?显然bfs每个点只走一遍以及终点只更新一次就是要靠入队顺序(因为队列中的点都是按照最短路排序的,相当于单调队列),否则就会答案错误(破坏了队列的单调性)。

于是既然我们要保持有序性那就直接把边权为0的u->v的v直接插入到队首即可,然后v马上就会被更新,于是上面的问题解决了 。

不难发现在有解的情况下队列扩展范围会不超过题中所给的m和最后的答案的最大值。

期望复杂度O(kn*n),k在无解时最大,否则一般情况下会因为bfs更早退出而变小(每条3的边被拆了之后最多3条边,每个空点最多拓展4条边)

#include <cstdio>
#include <cctype>
#include <cstring>
#include <deque>
using namespace std;
#define MAXN 105
#define MAXM 100010
#define MAXP 100100
char buf[1000001], *p1 = buf, *p2 = buf;
inline char get_char(){
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read(){
    int num = 0;
    char c;
    while(isspace(c = get_char()));
    while(num = num * 10 + c - 48, isdigit(c = get_char()));
    return num;
}
inline int min(int a, int b){
    int c = (a - b) >> 31;
    return (a & c) | (b & ~ c);
}
int n, m, tot = 1, dis[MAXM];
int beginx[MAXM], endx[MAXM], nxt[MAXM], h;
bool has[MAXM], vis[MAXM];
short matrix[MAXN][MAXN];
inline int Get_Pos(int i, int j){
    return ((i - 1) * n + j - 1) << 1;
}
inline void add_edge(int u, int v, bool c){
    nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, has[tot] = c;
    nxt[++tot] = beginx[v], beginx[v] = tot, endx[tot] = u, has[tot] = c;
}
inline void edge(int u, int v, int c){
    int tmp = ++h;
    switch(c){
        case 2:
            nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = tmp, has[tot] = true;
            nxt[++tot] = beginx[tmp], beginx[tmp] = tot, endx[tot] = v, has[tot] = true;
            break;
        case 3:
            nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = tmp, has[tot] = true;
            nxt[++tot] = beginx[tmp], beginx[tmp] = tot, endx[tot] = tmp = ++h, has[tot] = true;
            nxt[++tot] = beginx[tmp], beginx[tmp] = tot, endx[tot] = v, has[tot] = true;
            break;
    }
}
inline void add_edges(int u, int v, int c){
    nxt[++tot] = beginx[u], beginx[u] = tot, endx[tot] = v, has[tot] = c;
    edge(v, u, c + 2);
}
deque<int> mession;
inline void bfs(int s){
    bool flag = matrix[n][n];
    int tmp = Get_Pos(n, n) + matrix[n][n];
    int tmp1 = Get_Pos(n, n) + 1, tmp2 = Get_Pos(n, n) + 2;
    mession.push_back(s);
    dis[s] = 0, vis[s] = true;
    int u, v;
    while(!mession.empty()){
        u = mession.front(), mession.pop_front();
        for(int i = beginx[u]; i; i = nxt[i]){
            v = endx[i];
            if(vis[v]) continue;
            vis[v] = true;
            dis[v] = dis[u] + has[i];
            if(flag){
                if(dis[tmp] != -1) return ;
            } else if(dis[tmp1] != -1 && dis[tmp2] != -1) return ;
            if(has[i] || mession.empty()) mession.push_back(v);
            else mession.push_front(v);
        }
    }
}
int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; i++){
        int x = read(), y = read();
        matrix[x][y] = read() + 1;
    }
    h = (n * n) << 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int tmp = matrix[i][j], t = Get_Pos(i, j) + tmp;
            if(!tmp){
                int tx = Get_Pos(i, j);
                int tmp1 = matrix[i + 1][j], t1 = Get_Pos(i + 1, j) + tmp1, tmp2 = matrix[i][j + 1], t2 = Get_Pos(i, j + 1) + tmp2;
                int tmp3 = matrix[i - 1][j], t3 = Get_Pos(i - 1, j) + tmp3, tmp4 = matrix[i][j - 1], t4 = Get_Pos(i, j - 1) + tmp4;
                if(tmp1) add_edges(tx + tmp1, t1, 0), add_edges(tx + 3 - tmp1, t1, 1);
                if(tmp2) add_edges(tx + tmp2, t2, 0), add_edges(tx + 3 - tmp2, t2, 1);
                if(tmp3) add_edges(tx + tmp3, t3, 0), add_edges(tx + 3 - tmp3, t3, 1);
                if(tmp4) add_edges(tx + tmp4, t4, 0), add_edges(tx + 3 - tmp4, t4, 1);
                continue;
            }
            int tmp1 = matrix[i + 1][j], t1 = Get_Pos(i + 1, j) + tmp1, tmp2 = matrix[i][j + 1], t2 = Get_Pos(i, j + 1) + tmp2;
            if(tmp1) add_edge(t, t1, !(tmp == tmp1));
            if(tmp2) add_edge(t, t2, !(tmp == tmp2));
        }
    }
    memset(dis, -1, sizeof(dis));
    bfs(matrix[1][1]);
    int tmp = Get_Pos(n, n);
    if(matrix[n][n]) printf("%d", dis[tmp + matrix[n][n]]);
    else printf("%d", min(dis[tmp + 1], dis[tmp + 2]));
    return 0;
}