2.7k字2 分钟

首先考虑建图，因为 每个男孩最多只愿意和个不喜欢的女孩跳舞，而每个女孩也最多只愿意和个不喜欢的男孩跳舞。 所以对于每个男孩女孩均要建一个辅助点，到该点的权值为，对于互相喜欢的男女孩相连，权值为，对于不喜欢的，则他们的辅助点相连，权值亦为。 接下来考虑源点到男孩与女孩到汇点的权值情况。 1.如果权值小于等于答案，计最大流为，则满足 2.权值大于答案，则有 所以，我可以用遍历权值从到的情况，得到答案，也可二分来做 坑点：忘记女孩也要满足小于等于 const int N = 2e4 + 86; struct egdes { int to, nxt, w; } e[N * 2]
2.3k字2 分钟

最小割，注意边e要估好，不然RE走起 const LL N = 5e3 + 86; LL n, m; //n+1,n+2起始和终点，n+3以后虚点 struct edges { int to, nxt,w; } e[N*200]; int tot = 1, hd[N*100], cur[N*100]; void add(int x, int y, int v) { e[++tot]=(edges){y,hd[x],v};hd[x]=tot; } int lv
1.4k字1 分钟

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(){
1.6k字1 分钟

洛谷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) &
1.5k字1 分钟

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