Starry

P1345 [USACO5.4]奶牛的电信Telecowmunication 转化为最小割，注意起始点为i+n const int N=12000+96; struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1; void add(int u,int v,int w){ e[++tot]=(edge){v,hd[u],w}; hd[u]=tot; } int n,m,s,su,lv[N]; int bfs(){

洛谷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) &

用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],

最大流问题，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

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