关于存图

rsg26 @ 2021-09-03 18:17:57

by lotus_f @ 2021-09-03 18:22:26

u1s1 vector 属于邻接表，但是我感觉邻接表和链式前向星是一样的

by rsg26 @ 2021-09-03 18:23:32

@lotus_f az 不过您知道为啥会出现这种情况吗

by rsg26 @ 2021-09-03 18:24:06

就当我想问为啥 vector 比数组快（

by YamadaRyou @ 2021-09-03 18:54:48

@Rsg26 因为连续访问，用前向星或许更快

by 墨笙_Mooos @ 2021-09-03 18:55:33

@Rsg26 边数少罢 通常边数少的话vector挺快的

by 墨笙_Mooos @ 2021-09-03 18:56:33

一般树上问题存边就是因为边少采用vector存边的罢)

by hjxhjx @ 2021-09-03 18:57:24

写法问题吧...没听说过什么东西能比数组还快（除了bitset代替bool数组）

by YamadaRyou @ 2021-09-03 18:57:33

@墨笙_Mooos 我记着边数多的情况vector才快吧

by 墨笙_Mooos @ 2021-09-03 18:59:17

@WA王子 并不)

by rsg26 @ 2021-09-03 19:04:06

@墨笙_Mooos @WA王子 thx

@hjxhjx 您能帮帮我这个菜鸡看看写法哪里有问题吗

#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;
}