# [P1361](https://www.luogu.com.cn/problem/P1361)
> 小P有 $ n $ 中作物的种子，每种作物的种子有 $ 1 $ 个（就是可以种一棵作物）。
>
> 第i种作物种植在A中种植可以获得 $ a_i $ 的收益，在B中种植可以获得 $ b_i $ 的收益。
由这里可以看出，**对于每一株作物，仅能种在 A/B 的一块田地里**，也就是**二选一**。
那么我们想一想最小割的做法，通俗点来说就是：**对于每条路径，切去最小的那条边，以达到路径断裂且代价最小**，也就是**多选一**。
那么可否理解为：**对于 $ S->plant->T $ 的一条路径，选择其中的一条边，拆掉，接着另一个就是我答案中的边**。
那么原题的基本部分就转换成最小割了。
> 而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则中共有 $ m $ 种作物组合，第i个组合中的作物共同种在A中可以获得 $ {c_1}_i $ 的额外收益，共同总在B中可以获得 $ {c_2}_i $ 的额外收益。
对于这种情况，我们可以将这个点集打包。
建立一个新的点 $ X $ ，用 $ X $ 代表这一点集。
那么用 **$ S->X $** 来表示 **$ S->\{1,2\} $** 。
所以有：
同样，建立一个 **$ X' $** ，用于 $ {c_2}_i $ 的打包：
所以割边时怎么保证**只割 $ S->X $ 和 $ S->X' $** 呢？
当然是让我们**无法割去不想割的边**啦！
让不想割的边变成 $ INF $ ，算法就能过滤掉它~~（它绝不会傻到以 $ INF $ 的代价割边的）~~
所以**建图**就完成了！
接下来**跑一边 Dinic** 就完事儿啦！
可是我们是最小割（最大流）啊，这**不是答案**啊？
对，这确实不是答案。但是 Dinic 完之后我们已经“割去了”一些边，“完成了”最小割，也就是**完成了对于所有方案的不优解法的去除，剩下的自然就是最优方案。**~~（不信的话可以推一下样例）~~
那么**答案就是 总边权和 减去 最小割（最大流）**。
于是完成！
~~码风邪教勿喷~~
```cpp
/*
■■■ ■ ■ ■ ■■■■ ■■■ ■■ ■ ■ ■■■■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■■ ■ ■
■■■ ■ ■ ■ ■■■■ ■ ■ ■ ■ ■■ ■ ■■■■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■■ ■
■■■ ■■■■ ■■ ■■■■ ■■■ ■■ ■ ■■ ■■■■
*/
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
using namespace std ;
typedef long long lint ;
typedef long double ntrl ;
# define MAXN 1000010
# define MAXM 1000010
# define INF 0x3f3f3f3f
///globle varible///
int n , m ;
int sumval ;
/////*/
///basic function///
inline lint min ( lint x , lint y ) { return x < y ? x : y ; }
inline lint max ( lint x , lint y ) { return x > y ? x : y ; }
inline bool isltr ( char x ) { return ( 'A' <= x && x <= 'Z' ) || ( 'a' <= x && x <= 'z' ) ; }
inline bool isnum ( char x ) { return ( '0' <= x && x <= '9') ; }
/////*/
///fast read///
inline lint readlint ( )
{
lint val = 0 , sign = 1 ; char tmp = getchar ( ) ;
while ( ! isnum ( tmp ) ) { if ( tmp == '-' ) { sign = - sign ; } tmp = getchar ( ) ; }
while ( isnum ( tmp ) ) { val = ( val << 1 ) + ( val << 3 ) + tmp - 48 ; tmp = getchar ( ) ; }
return val * sign ;
}
inline char readlter ( )
{
char tmp = getchar ( ) ;
while ( ! isltr ( tmp ) )
tmp = getchar ( ) ;
return tmp ;
}
/////*/
///adjacency list///
struct edge
{
int to ;
int last ;
int cap ;
} e [ MAXM * 2 ] ;
int list [ MAXN ] , edgecnt = 1 ;
inline void addedge ( int u , int v , int c )
{
e [ ++ edgecnt ] . to = v ;
e [ edgecnt ] . last = list [ u ] ;
e [ edgecnt ] . cap = c ;
list [ u ] = edgecnt ;
}
/////*/
///dinic///
int s , t ;
int depth [ MAXN ] ;
deque < int > que ;
int cur [ MAXN ] ;
inline void dinic_addedge ( int u , int v , int c )
{
addedge ( u , v , c ) ;
addedge ( v , u , 0 ) ;
}
inline int dinic_bfs ( )
{
memset ( depth , 0 , sizeof ( depth ) ) ;
que . clear ( ) ;
depth [ s ] = 1 ;
que . push_back ( s ) ;
while ( ! que . empty ( ) )
{
for ( int i = list [ que . front ( ) ] ; i ; i = e [ i ] . last )
{
if ( ! depth [ e [ i ] . to ] && e [ i ] . cap )
{
depth [ e [ i ] . to ] = depth [ que . front ( ) ] + 1 ;
que . push_back ( e [ i ] . to ) ;
}
}
que . pop_front ( ) ;
}
return depth [ t ] ;
}
inline int dinic_dfs ( int now , int mxflow )
{
if ( now == t )
{
return mxflow ;
}
int flow = 0 ;
for ( int &i = cur [ now ] ; i ; i = e [ i ] . last )
{
int v = e [ i ] . to ;
if ( depth [ v ] == depth [ now ] + 1 && e [ i ] . cap )
{
int f = dinic_dfs ( v , min ( e [ i ] . cap , mxflow ) ) ;
if ( f )
{
e [ i ] . cap -= f ;
e [ i ^ 1 ] . cap += f ;
mxflow -= f ;
flow += f ;
if ( ! mxflow )
{
return flow ;
}
}
}
}
return flow ;
}
inline int dinic ( )
{
int allflow = 0 ;
while ( dinic_bfs ( ) )
{
memcpy ( cur , list , sizeof ( cur ) ) ;
int f ;
while ( ( f = dinic_dfs ( s , INF ) ) )
{
allflow += f ;
}
}
return allflow ;
}
/////*/
int main ( )
{
n = readlint ( ) ;
s = 0 ;
t = n + 1 ;
for ( int i = 1 , w ; i <= n ; i ++ )
{
w = readlint ( ) ;
dinic_addedge ( s , i , w ) ;
sumval += w ;
}
for ( int i = 1 , w ; i <= n ; i ++ )
{
w = readlint ( ) ;
dinic_addedge ( i , t , w ) ;
sumval += w ;
}
m = readlint ( ) ;
for ( int i = 1 , cnt , tmp , val1 , val2 ; i <= m ; i ++ )
{
cnt = readlint ( ) ;
val1 = readlint ( ) ;
val2 = readlint ( ) ;
sumval += val1 + val2 ;
dinic_addedge ( s , t + ( i * 2 - 1 ) , val1 ) ;
dinic_addedge ( t + ( i * 2 ) , t , val2 ) ;
while ( cnt -- )
{
tmp = readlint ( ) ;
dinic_addedge ( t + ( i * 2 - 1 ) , tmp , INF ) ;
dinic_addedge ( tmp , t + ( i * 2 ) , INF ) ;
}
}
// Answer = SumEdgeWeight - MinimumCut
return 0 ;
}
```