题解 P3956 【棋盘】

Creeper_LKF

2017-11-16 21:05:15

Solution

\_一个提高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条边) ```cpp #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; } ```