u1s1 vector 属于邻接表，但是我感觉邻接表和链式前向星是一样的
by lotus_f @ 2021-09-03 18:22:26
@[lotus_f](/user/511689) az 不过您知道为啥会出现这种情况吗
by rsg26 @ 2021-09-03 18:23:32
就当我想问为啥 vector 比数组快（
by rsg26 @ 2021-09-03 18:24:06
@[Rsg26](/user/487027) 因为连续访问，用前向星或许更快
by YamadaRyou @ 2021-09-03 18:54:48
@[Rsg26](/user/487027) 边数少罢 通常边数少的话vector挺快的
by 墨笙_Mooos @ 2021-09-03 18:55:33
一般树上问题存边就是因为边少采用vector存边的罢)
by 墨笙_Mooos @ 2021-09-03 18:56:33
写法问题吧...没听说过什么东西能比数组还快（除了bitset代替bool数组）
by hjxhjx @ 2021-09-03 18:57:24
@[墨笙_Mooos](/user/78216) 我记着边数多的情况vector才快吧
by YamadaRyou @ 2021-09-03 18:57:33
@[WA王子](/user/203008) 并不)
by 墨笙_Mooos @ 2021-09-03 18:59:17
@[墨笙_Mooos](/user/78216) @[WA王子](/user/203008) thx
@[hjxhjx](/user/178480) 您能帮帮我这个菜鸡看看写法哪里有问题吗
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NR = 205;
const int MR = 40000 + 5;
const int XR = 315170 + 5;
struct Edge
{
int u, v, next;
} e[XR];
int n, m, s[NR][NR], res, h[MR], en, match[MR];
bool vis[MR];
inline int getind(int x, int y)
{
if (x < 1 || x > n || y < 1 || y > n || s[x][y]) return 0;
return n * (x - 1) + y;
}
inline int dfs(int x)
{
for (register int i = h[x]; i; i = e[i].next)
{
int v = e[i].v;
if (!vis[v])
{
vis[v] = 1;
if (!match[v] || dfs(match[v]))
{
match[x] = v, match[v] = x;
return 1;
}
}
}
return 0;
}
inline void add(int u, int v)
{
if (!u || !v) return;
en ++;
e[en].u = u, e[en].v = v;
e[en].next = h[u], h[u] = en;
}
int main()
{
scanf("%d %d", &n, &m), res = n * n - m;
for (register int i = 1; i <= m; ++i)
{
int u, v;
scanf("%d %d", &u, &v), s[u][v] = 1;
}
for (register int i = 1; i <= n; ++i)
for (register int j = 1; j <= n; ++j)
if (!s[i][j])
add(getind(i, j), getind(i + 1, j + 2)), add(getind(i, j), getind(i + 1, j - 2)),
add(getind(i, j), getind(i - 1, j + 2)), add(getind(i, j), getind(i - 1, j - 2)),
add(getind(i, j), getind(i + 2, j + 1)), add(getind(i, j), getind(i + 2, j - 1)),
add(getind(i, j), getind(i - 2, j + 1)), add(getind(i, j), getind(i - 2, j - 1));
for (register int i = 1; i <= n; ++i)
for (register int j = 1; j <= n; ++j)
if (i + j & 1 && !s[i][j]) memset(vis, 0, sizeof(vis)), res -= dfs(getind(i, j)) == 1;
printf("%d\n", res);
return 0;
}
```
by rsg26 @ 2021-09-03 19:04:06