模型描述
有一个工厂，接到了 $n$ 个订单，为了完成这些订单，工厂需要采购一些机器，一共可采购 $m$ 台机器。我们知道完成每个订单的收益，也知道购买某个机器的开销。一个订单需要对应地购买某些机器，一台机器可以同时完成多个订单。现在工厂决定选择性地接一些订单，使得工厂的利润最大化。
最大权闭合子图
我们来介绍一下什么是最大权闭合图。
闭合子图
定义一个有向图 $G(V,E)$ 的闭合子图为该有向图的一个子图 $G′(V′,E′)$ ,子图中每一个点的出边都指向这个子图里的点。例如下图就是一个闭合图。
最大权闭合子图
给每个顶点 $i$ 分配一个权值 $w_i$ ，最大权闭合子图就是点权总和 $\sum_{i∈V′} w_i$ 最大的闭合子图。
那么我们如何找到最大权闭合子图呢？
一般我们会将其转化为网络流模型。
具体来说：在原图的基础上新增加源点 $S$ 和汇点 $T$ ，原图所有边的流量设置为 $\text{INF}$ ,对于每一个边权为正的边，源点向其连一条流量为该点点权的边，对于每一个边权为负的边，这个点向汇点连一条流量为点权的绝对值的边。那么最大的权就是点权为正的点的点权和减去最小割，例如上图的例子可以转化为：
如何算方案呢？与源点相连的点都是最大权闭合子图的顶点。
证明
那么这个为什么是对的呢？我们尝试来证明它。
引理一：这个网络的最小割一定是一个简单割，也就是只会割直接与源点/汇点相连的边。
证明显然，没有与源点/汇点相连的边都是正无穷。
引理二：该图的每一个简单割产生的两个子图，我们记含有源点的图为 $S$ ，记含有汇点的图为 $T$ ，则图 $S$ 为闭合子图。
由于是简单割，所以 $S$ 中的任何一个节点都不能到达 $T$ ,所以该引理正确。
证明：最小割产生的图 $S$ 和 图 $T$ ，图 $S$ 为最大权闭合子图</h4>
因为割集中所有的边，不是连接到 $S$ 上，就是连接在 $T$ 上（引理一）。
我们记割边权值和为 $X$ ，割集中连接到源点的边的权值和为 $x_1$ ，连接到汇点的权值和为 $x_2$ ，则有 $X=x_1+x_2$ 。
记图 $S$ 的所有点的权值和为 $W$ ，记期中正权值之和为 $w_1$ ，负权值之和为 $−w2$ ，有 $W=w_1−w_2$ 。
所以有 $W+X=w_1−w_2+x_1+x_2$ 。
注意到 $x_2=w_2$ （图 $S$ 中点权为负的点一定一开始连接到汇点，后来被加入割集），可得 $W+X=w_1+x_1$ 。
显然 $w_1+x_1$ 是图中正点权权值和，记为 $SUM$ 。
因此 $W=SUM−X$ 。由引理二得知 $S$ 为一个闭合子图。$SUM$ 是一个定值，我们要使 $X$ 尽可能的小，也就是求最小割。
如何建模
我们把订单和机器都看成一些点，订单都为正边权，机器为负边权，订单指向这个订单需要的机器，显然这个图的最大权独立集就是答案（满足所有订单的最大收益方案）。
代码
（以链接里的题目代码为准，大同小异）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define RFOR(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2000+5;
struct Node{
struct Edge *first,*cur;
int level;
}node[MAXN];
struct Edge{
Node *s,*t;
Edge *next,*rev;
int cap,flow;
}pool[1000000],*frog = pool;
Edge *New(Node *s,Node *t,int cap){
Edge *ret = ++frog;
*ret = (Edge){s,t,s->first,NULL,cap,0};
return ret;
}
inline void add(int u,int v,int cap,int rev=0){
node[u].first = New(&node[u],&node[v],cap);
node[v].first = New(&node[v],&node[u],rev);
node[u].first->rev = node[v].first;
node[v].first->rev = node[u].first;
}
int N,S,T;
bool bfs(Node *s,Node *t){
FOR(i,0,N){
node[i].cur = node[i].first;
node[i].level = 0;
}
std::queue<Node *> q;
s->level = 1;q.push(s);
while(!q.empty()){
Node *v = q.front();q.pop();
for(Edge *e = v->first;e;e = e->next){
if(e->flow < e->cap && !e->t->level){
e->t->level = v->level + 1;
if(e->t == t) return true;
q.push(e->t);
}
}
}
return false;
}
int dfs(Node *v,Node *t,int limit = INT_MAX){
if(v == t) return limit;
int flow;
for(Edge *&e = v->cur;e;e = e->next){
if(e->flow < e->cap && e->t->level == v->level + 1){
if((flow = dfs(e->t,t,std::min(limit,e->cap-e->flow)))){
e->flow += flow;
e->rev->flow -= flow;
return flow;
}
}
}
return 0;
}
int dinic(){
int ans=0,flow;
while(bfs(&node[S],&node[T])){
while((flow = dfs(&node[S],&node[T]))){
ans += flow;
}
}
return ans;
}
int n,m,sum;
int main(){
scanf("%d%d",&n,&m);
N = n+m+1;
S = 0,T = N;
FOR(i,1,m){
int x;scanf("%d",&x);
add(i+n,T,x);
}
FOR(i,1,n){
int a,k;
scanf("%d%d",&a,&k);
sum += a;add(S,i,a);
FOR(j,1,k){
int x;scanf("%d",&x);
add(i,x+n,INT_MAX);
}
}
printf("%d\n",sum-dinic());
// system("pause");
return 0;
}