题目大意

给定一张$n$个点$m$条边的有向图，每条边都有一个容量$c$和一个扩容费用$w$（这里扩容费用是指将容量扩大$1$所需的费用）

询问

1. 在不扩容的情况下，$1$到$n$的最大流

2. 将$1$到$n$的最大流增加$k$所需的最小扩容费用

阅读更多……

题目大意

给出一个有$n$个点$m$条边的无向图

求至少要删掉几个点，使得新图存在两个点无法联通

阅读更多……

题目大意

阅读更多……

题目大意

有$m$个项目和$n$个员工

做项目$i$可以获得$A_i$元，但是必须雇用若干个指定的员工。雇用员工$j$需要花费$B_j$元，且一旦雇用，员工$j$可以参加多个项目的开发

问经过合理的项目取舍,最多能挣多少钱

阅读更多……

题目大意

YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为$n\times n$个区域。YT城市中包括$(n+1)\times (n+1)$个交叉路口和$2\times n\times(n+1)$条双向道路，每条双向 道路连接主干道上两个相邻的交叉路口。

小Z作为市长统计到了每条道路的人流量$w_i$，然而每个点都有一定的海拔$h_i(0\leqslant h_i\leqslant 1)$，那么经过一条道路需要耗费的体力值为$w_i\times max(0,h_{终点}-h_{起点})$

已知起点为右上角，海拔为0，终点为左下角，海拔为1，求最少耗费多少体力值。

顺便给出样例的图

阅读更多……

题目大意

给出m个通讯站建造成本$A_i$

给出n个用户，只要建造了他需要的两个通讯站就能得到收益$C_i$

求出最大获利(获利=总收益-总成本)

阅读更多……

题目大意

源点为 (1,1)，汇点为 (n,m) (上图中n=4,m=4)。有以下三种类型的道路

• (x, y) <==> (x+1, y)

• (x, y) <==> (x, y+1)

• (x, y) <==> (x+1, y+1)

每条无向边边权＞0，求最小割。

阅读更多……