洛谷P1343地震逃生_Dinic
洛谷P1343最大流问题的Dinic解法,bfs分层然后dfs增广,还得捋捋弧优化
因为在Dinic算法中,一条边增广一次后就不会再次增广了,所以下次增广时不需要再考虑这条边。我们把head数组复制一份,但不断更新增广的起点。
UPD:原来是这里写错了
```cpp
for(int eg=hd[p];eg;eg=e[eg].nxt)
```
应该是
```cpp
for (int eg = cur[p]; eg && r; eg = e[eg].nxt)
&
more...洛谷P1343地震逃生_EK
用EK算法来做最大流问题,相较于FF算法,EK算法先用bfs找出最小流,然后从汇点开始扣减容量到汇点
const int N = 2e3 + 86;
struct edge
{
int to, nxt, w;
} e[N * 2];
int hd[N], tot = 1;
void add(int u, int v, int w)
{
e[++tot] = (edge){v, hd[u], w};
hd[u] = tot;
}
int n, m, x, flow[N],
more...洛谷P1343地震逃生
最大流问题,FF算法:
链式前向星建边,异或来求反向边。
const int N=2e3+86;
struct edge{int to,nxt,w;}e[N*2];int hd[N],tot=1;
void add(int u,int v,int w){
e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}
int n,m,x;
bitset<286> vis;
int dfs(int p,int flow){
if(p
more...