好长时间不做网络瘤了，啥也不会，于是复健了下。
导致现在我看到网络瘤就恶心。
大部分都是题，还有一小部分也是题。
在这里放个歌词罢。
\(\textbf{Born in the month of darkness}\)
Before the Great Burning, before the wars
A time of nothing, but hills and shores
The smoke of cities, and fields of rye
No eyes or voices beyond the sky
Believers roamed from town to town
They spied every baby born, up and down
Scouring the land for a child to use
And ponderous, esoteric clues
A crumbling black city, an outcast found
Father a monster, mother under the ground
A beggar, a mongrel, a boy with no shoes
He fell to their hands to cage and abuse
And lo! In the month of darkness
And lo! His name destroyed
And lo! He still whispers in silence
And lo! He went into the void
They were drawn to a light, a waning gray
His face was blank, he had nothing to say
He watched and waited, they painted his eyes
They colored his clothing with pigments and dyes
They found a path away from the light
To an ancient tree withered by blight
A sacred altar, encircled in stones
Twin blades of bronze, sharpened on bones
And lo! In the month of darkness
And lo! His name destroyed
And lo! He still whispers in silence
And lo! He went into the void
In the Month of Darkness, seasons destroyed
A ritual killing bound his spirit to the Void
Eyes drained of color, the beggar no more
To become what the Believers waited for
They set him outside, beyond the spheres
Quiet as the night, long like the years
He opened his eyes, as black as a dream
Trying to speak, his only words a scream
And lo! In the month of darkness
And lo! His name destroyed
And lo! He still whispers in silence
And lo! He went into the void
以下用 \((u,v,w)\) 表示网络流建模中从 \(u\) 到 \(v\) 容量为 \(w\) 的边。
用 \((u,v,w,c)\) 表示网络流建模中从 \(u\) 到 \(v\) 容量为 \(w\) ，费用为 \(c\) 的边。
用 \((u,v)\) 表示原图中 \(u\) 与 \(v\) 的连边关系。
酒店之王
发现房间，菜品，客人都有一定的限制。考虑让客人作为流量，求出的最大流即是答案。
如果把房间 \(p_i\) 和菜品 \(q_i\) 的限制都放在客人的同一侧，那么每个房间/菜品只能提供给一个客人的条件将不会被同时满足。所以应该把每位客人当做容量为 \(1\) 的边放在最中间，两头向喜欢的房间 \(p_i\) 或者菜品 \(q_i\) 相连，再连边 \((s,p_i/q_i,1),(q_i/p_i,t,1)\) 表示两者皆只能被选择一次。
跑最大流即可。
[SHOI2001]小狗散步
主人在一个位置走在另一个位置的途中，狗最多只能前往一个景点，一个景点只能经过一次。于是可以将主人的每一段路程看做一个节点 \(x_i\)，景点看做 \(y_i\)。处理出第 \(i\) 段路程小狗能够到达的景点 \(y_j\)。连边 \((s,x_i,1),(x_i,y_j,1),(y_i,t,1)\)，跑最大流。
输出方案只需要看边 \((x_i,y_j,1)\) 是否满流即可，满流就输出 \(y_j\) 。
追查坏牛奶 Pollutant Control
第一问，一眼顶针，裸的最小割。
第二问问的是最小割中所要割掉的最少割边。
考虑第一问搞完之后的残量网络，所有满流的边都可以成为最小割，将这些满流边的容量设为 \(1\)，其他边的容量设为 \(inf\)。此时可以发现每一单位的流量都会表示一条边的割去，为满足条件再对其跑一次最小割即可。
拍照
最大权闭合子图的模型。
对于所有的收入设点 \(x_i\)，连边 \((s,x_i,m_i)\)。所有的费用设点 \(y_i\)，连边 \((y_i,t,n_i)\)。对于每一种关系，连边 \((x_i,y_i,inf)\)。表示若得到某收入就必须进行某花费，否则就减去该收入。
初始化 $ans=\sum_{i=1}^{M} m_i $，减去上图的最小割即可。
人员雇佣
三个月之前做过的题再看一遍还tm不会
标签：复健,连边,费用,网络,新鲜,最小,Link,textrm From： https://www.cnblogs.com/Broken-Eclipse/p/17138916.html