luoguP1361 小M的作物

题目描述

小 M 在 MC 里开辟了两块巨大的耕地 \(A\) 和 \(B\)（你可以认为容量是无穷），现在，小 P 有 \(n\) 种作物的种子，每种作物的种子有 \(1\) 个（就是可以种一棵作物），编号为 \(1\) 到 \(n\)。

现在，第 \(i\) 种作物种植在 \(A\) 中种植可以获得 \(a_i\) 的收益，在 \(B\) 中种植可以获得 \(b_i\) 的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小 M 找到了规则*有 \(m\) 种作物组合，第 \(i\) 个组合中的作物共同种在 \(A\) 中可以获得 \(c_{1,i}\) 的额外收益，共同种在 \(B\) 中可以获得 \(c_{2,i}\) 的额外收益。

小 M 很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？

解法：

这是一道非常经典的二者取一类的最小割的题目。

对任意一种作物，我们让源点向他的连边的容量为在 \(A\) 中种植的收益，他向汇点的连边的容量为在 \(B\) 中种植的收益（反过来也可以）。

在这类题中，割掉的边意味着不选，留下的边是这个节点的选择，比如如果留下了这个点到汇点的连边，那么这就意味着这种作物不在 \(A\) 中种，在 \(B\) 中种。

接下来考虑如何统计同在 \(A\) 中种植的收益和同在 \(B\) 中种植的收益。因为这两种本质相同，我们就只讨论同在 \(A\) 中种植的收益。我们对新建一个节点表示这种方案，源点向这个点的连边的容量就是存在这种方案的价值，这个点再向所有包括在这种方案在内的节点连一条权值为 \(INF\) 的边。

在最小割中如果有权值为 \(INF\) 的边，就意味着这条边不可割。

为什么这样子是对的呢？对任意一个在这个方案中的节点，如果他割掉的是与源点的连边，留下的是与汇点的连边，那么这个方案所代表的节点与源点的连边也要割掉，不然就存在一条 "源点—方案节点—当前节点—汇点" 这样一条路径使源点可以到达汇点，显然这是不行的，而且我们已经割掉了和源点的连边，意味着我们 必须 要留下和汇点的连边，而方案节点和当前节点的连边权值是 \(INF\)，是一条不可割边，所以我们只能把 "源点—方案节点" 这条边给割掉。

同理，同在 \(B\) 中种植的作物就是将作物代表的节点连线当前代表这个方案的节点，权值为 \(INF\)；这个方案的节点连向汇点，权值是这种方案的价值。

最后求最小割就可以了。

Code：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std ;

const int INF = 0x3f3f3f3f ;
int n , m , s , t , tot , dis[20005] , ans = 0 ;

struct Edge
{
	int nxt , to , len ;
} edge[4000005] ;

int cnt = 1 , head[20005] ;
void insert ( int u , int v , int w )
{
	edge [ ++ cnt ] .nxt = head [ u ] ;
	edge [ cnt ] .to = v ;
	edge [ cnt ] .len = w ;
	head [ u ] = cnt ;
}

queue < int > q ;
bool bfs ( )
{
	memset ( dis , 0 , sizeof ( dis ) ) ;
	dis [ s ] = 1 ;
	q .push ( s ) ;
	while ( ! q .empty ( ) )
	{
		int x = q .front ( ) ; q .pop ( ) ;
		for ( int i = head [ x ] ; i ; i = edge [ i ] .nxt )
		{
			int y = edge [ i ] .to ;
			if ( dis [ y ] || ! edge [ i ] .len )
				continue ;
			dis [ y ] = dis [ x ] + 1 ;
			q .push ( y ) ;
		}
	}
	return dis [ t ] ;
}

int dfs ( int x , int now )
{
	if ( x == t )
		return now ;
	int res = now ;
	for ( int i = head [ x ] ; i && res ; i = edge [ i ] .nxt )
	{
		int y = edge [ i ] .to ;
		if ( dis [ y ] != dis [ x ] + 1 || ! edge [ i ] .len )
			continue ;
		int w = dfs ( y , min ( res , edge [ i ] .len ) ) ;
		if ( ! w ) dis [ y ] = 0 ;
		edge [ i ] .len -= w ;
		edge [ i ^ 1 ] .len += w ;
		res -= w ;
	}
	return now - res ;
}

int main ( )
{
	cin >> n ; tot = n ;
	s = ++ tot ;
	t = ++ tot ;
	for ( int i = 1 ; i <= n ; ++ i )
	{
		int x ;
		cin >> x ;
		insert ( s , i , x ) ;
		insert ( i , s , 0 ) ;
		ans += x ;
	}
	for ( int i = 1 ; i <= n ; ++ i )
	{
		int x ;
		cin >> x ;
		insert ( i , t , x ) ;
		insert ( t , i , 0 ) ;
		ans += x ;
	}
	cin >> m ;
	for ( int i = 1 ; i <= m ; ++ i )
	{
		int k , c1 , c2 , si , ti ;
		cin >> k >> c1 >> c2 ;
		ans += c1 + c2 ;
		si = ++ tot ;
		ti = ++ tot ;
		insert ( s , si , c1 ) ;
		insert ( si , s , 0 ) ;
		insert ( ti , t , c2 ) ;
		insert ( t , ti , 0 ) ;
		for ( int j = 1 ; j <= k ; ++ j )
		{
			int x ;
			cin >> x ;
			insert ( si , x , INF ) ;
			insert ( x , si , 0 ) ;
			insert ( x , ti , INF ) ;
			insert ( ti , x , 0 ) ;
		}
	}
	int tmp = 0 ;
	while ( bfs ( ) )
		while ( tmp = dfs ( s , INF ) )
			ans -= tmp ;
	cout << ans << '\n' ;
	return 0 ;
}