题解 P3956 【棋盘】
Creeper_LKF
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条边)
```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;
}
```