Starry

考虑到问题 能使最多顾客满意呢 所以我们应以客人为主要限制目标，所以将其放中间，两边各连房间和菜，于是便可转化为最大流问题 建图应注意到客人只要一个，所以对每个客人应建两点，相连的权值为1，左边点与房间相连，右边点与菜相连 const int N = 2e5 + 86; struct egdes { int to, nxt, w; } e[N * 2]; int hd[N * 2], cur[N * 2], tot = 1, st, en; vi lv; void add(int x, int y, int w) { e[

对于同意午睡的，源点到该点权值为1，该点到源点权值为0. 而对于好朋友，则两点建立双向边，权值均为1 对于多对好朋友冲突，我们贪心地取最少的那一边使得总冲突数最少，对于此即为最小割最大流。 const int N=5e5+86; struct egdes{ int to,nxt,w; }e[N*2];int hd[N*2],cur[N*2],tot=1,st,en; vi lv; void add(int x,int y,int w){ e[++tot]=(egdes){y,hd[x],w};

最大流问题，建图时注意每排座位有两人 const int N=2e4+86; struct egdes{ int to,nxt,w; }e[N*2];int hd[N*2],cur[N*2],tot=1,st,en; vi lv; void add(int x,int y,int w){ e[++tot]=(egdes){y,hd[x],w}; hd[x]=tot; } int bfs(){ lv.assign(N,0); memcpy(cur

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