LG 1791 [国家集训队]人员雇佣

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转一定是我做题太少了看不出这是个最小割我们将每个人看成一个点,然后如下建边:源点向每个人连流量为其总收益的边($\sum{j=1}^n E{i,j}$)每个人向汇点连流量为其花费的边$i$向$j$连流量为$E_{i,j} \times 2$的边然后用所有能赚到的利润减去最小花费就可以了第三条,如果两个人都选,可以获得$E_{i,j}$的利润如果有一个不选,会亏损$E_{i,j}$的利润……