Description：

有一些任务，每个任务需要用到一些机器，机器可以买也可以租，租了只能用一次，选一些任务使得收益最大。

$1\leqslant n\leqslant 1200$

Solution：

不妨先考虑最大权闭合子图的本质，它的本质其实是最小割，因为割掉从源点到这个点的边代表放弃它失去这么多收益，割掉到汇点的边代表选择它花费这么多代价，如果这题没有租用那就是一个裸的最大权闭合子图了，考虑租用怎么办，肯定是在最大权闭合子图的基础上改进，发现还有一些容量为 $\infty$ 的边我们还没用过，把它换成租金会发现正好符合租用的意义，于是这样建边即可。

反正我没有想到。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1210

int s,t;

struct edge

{

	int to,nxt,f;

}e[(MAXN + MAXN + MAXN * MAXN) * 2];

int edgenum = 0;

int lin[MAXN + MAXN];

void add(int a,int b,int f)

{

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

int ch[MAXN + MAXN];

bool BFS()

{

	queue<int> q;q.push(s);

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	s = n + m + 1;t = s + 1;

	int sum = 0;

	int x,w,a,b;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&x,&w);

		sum += x;

		add(s,i,x);

		while(w--)

		{

			scanf("%d%d",&a,&b);

			add(i,a + n,b);

		}

	}

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&x);

		add(i + n,t,x);

	}

	cout << sum - dinic() << endl;

	return 0;

}