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