Dinic算法vector样例过不了求调

P3376 【模板】网络最大流

@[死在水中的鱼](/user/333800) 网络流的反向边和正向边咋一样呀 /fad ```cpp if(k==0) dis[to]=INF; G[x][i].w-=k; G[x][i].w+=k; res+=k; sum-=k; ``` 这里的 `G[x][i].w` 真的有实质改变么?
by 方123456 @ 2022-12-31 12:49:59


@[死在水中的鱼](/user/333800) 宁哪来的反边啊。要不邻接矩阵,要不就前向星。
by char_cha_ch @ 2022-12-31 12:52:23


@[方123456](/user/128754) 应该怎么写哦?
by qip101 @ 2022-12-31 12:56:36


@[死在水中的鱼](/user/333800) 应该是 ```cpp G[x][i].w-=k; G[反边].w+=k; ``` 链式前向星里,反边就是 `i ^ 1`,vector就很难存。 可以再额外开一个数组,记录每条边的反边。不过还是 链前 方便(
by liangbowen @ 2022-12-31 13:46:24


@[liangbowen](/user/367488) 反边应该就是G[i][x]?我改了以后还是输出0
by qip101 @ 2023-01-01 12:19:40


vector可以存边的指针。 而且,可以用map,但是带log。
by ssilrrr @ 2023-01-04 12:58:00


|