luoguP1361 small M crops

Title Description

Xiaom has opened up two huge cultivated lands \ (A \) and \ (B \) (you can think that the capacity is infinite). Now, Xiaop has \ (n \) seeds of crops, and there are \ (1 \) seeds of each crop (that is, one crop can be planted), numbered \ (1 \) to \ (n \).

Now, the \ (I \) crop can get \ (a_i \) income from planting in \ (A \), and \ (b_i \) income from planting in \ (B \). Moreover, there is such A magical phenomenon that some crops can get additional income from CO planting in A piece of cultivated land. Xiao m found the rule that there are \ (m \) crop combinations in total, For the crops in the \ (I \) combination, the co planting can obtain the additional income of \ (C {1, I} \) in \ (A \), and the co planting can obtain the additional income of \ (C {2, I} \) in \ (B \).

Xiao M quickly calculated the maximum benefit of planting, but he wanted to test you. Can you answer his question?

Solution:

This is a very classic problem of taking the minimum cut of one kind.

For any crop, we let the capacity of the source point to its edge be the income from planting in \ (A \), and the capacity of its edge to the sink be the income from planting in \ (B \) (vice versa).

In such questions, the cut edge means not to select, and the left edge is the choice of this node. For example, if the connecting edge from this point to the sink point is left, it means that this crop is not planted in \ (A \) but in \ (B \).

Next, consider how to count the benefits of planting in the same \ (A \) and planting in the same \ (B \). Because the two are essentially the same, we will only discuss the benefits of planting in the same \ (A \). We represent this scheme for A new node. The capacity of the edge connection from the source point to this point is the value of this scheme. This point connects an edge with A weight of \ (INF \) to all nodes included in this scheme.

In the minimum cut, if there is an edge with a weight of \ (INF \), it means that this edge is not cuttable.

Why is this right? For any node in this scheme, if it cuts off the edge with the source point and leaves the edge with the sink point, the edge with the source point represented by this scheme should also be cut off. Otherwise, there is a path of "source point - scheme node - current node - sink" so that the source point can reach the sink point. Obviously, this is not possible, Moreover, we have cut off the edge with the source point, which means that we must leave the edge with the sink point, and the edge weight of the scheme node and the current node is \ (INF \), which is a non cutting edge, so we can only cut off the edge of "source point scheme node".

Similarly, for the crops planted in the same \ (B \), connect the nodes represented by the crops to the nodes currently representing the scheme, and the weight is \ (INF \); The nodes of this scheme are connected to the sink, and the weight is the value of this scheme.

Finally, find the minimum cut.

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 ;
}