题目描述
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1...n编号）。
现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则***有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益。
小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？
输入格式
第一行包括一个整数n
第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，
对于接下来的第i行：第一个整数ki，表示第i个作物组合***有ki种作物，
接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。
输出格式
只有一行，包括一个整数，表示最大收益
输入输出样例
输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>
3 4 2 1 2 3 2 1 2 3 2 1 2
输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>
11
说明/提示
样例解释
A耕地种1，2，B耕地种3，收益4+2+3+2=11。
数据范围与约定
1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。
思路
如果把农作物作为中间点，农场 A 设为源， B 设为汇。
因为对于每个农作物只能种在一个农场中，所以该题可以等效为一个最小割模型。
所以如何对 bonus 的组合建边是关键。
把整个组合点集看作是一个点并拆成出入两点，由A有一条到入点的路，且从出点有一条到B的路，再逐次将待加入的点添加进点集就可以了。
这样能获得的最大值就是总价值 - 最小割
CODE
#include < cstdio >
#include < iostream >
#include < cstring >
#include < queue >
#include < vector >
#include < algorithm >
using namespace std ;
const int maxn = 1 e 6 + 7 ;
const int inf = 0x 3f3f3f3f ;
template < class T > inline void read(T & res )
{
char c ;T flag = 1 ;
while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}
struct edge { int from ,to ,cap ,flow ;};
struct isap
{
int n ,s ,t , p [maxn ], d [maxn ], cur [maxn ], num [maxn ];
bool vis [maxn ];
vector <int> g [maxn ];
vector <edge >edges ;
void init( int n , int s , int t ) {
this -> n = n ;
this -> s = s ;
this -> t = t ;
for( int i = 1 ;i <= n ;i ++ ) g [i ].clear();
edges .clear();
}
void addegde( int from , int to , int cap ) {
edges .push_back((edge ){from , to , cap , 0} );
edges .push_back((edge ){to , from , 0 , 0} );
int m = edges .size();
g [from ].push_back(m - 2 );
g [to ].push_back(m - 1 );
}
int augment() { ///找增广路
int x = t ,a = inf ;
while(x !=s ) {
a = min(a , edges [ p [x ]]. cap - edges [ p [x ]]. flow );
x = edges [ p [x ]]. from ;
}
x =t ;
while(x != s ) {
edges [ p [x ]]. flow += a ;
edges [ p [x ] ^ 1 ]. flow = -a ;
x = edges [ p [x ]]. from ;
}
return a ;
}
int maxflow() { ///更新最大流
int flow = 0 ;
memset(num , 0 , sizeof (num ));
memset(cur , 0 , sizeof (cur ));
for( int i = 1 ; i <= n ; i ++ ) num [ d [i ]] ++ ;
int x = s ;
while( d [s ] < n ) { ///最长的一条链上，最大的下标是nv-1，如果大于等于nv说明已断层
if(x == t ) {
flow += augment();
x = s ; //回退
}
bool ok = 0 ;
for( int i = cur [x ]; i < g [x ].size(); i ++ ) {
edge &e = edges [ g [x ][i ]];
if( d [x ] == d [ e . to ] + 1 && e . cap > e . flow ) {
p [ e . to ] = g [x ][i ];
cur [x ] = i ;x = e . to ;
ok = 1 ;
break;
}
}
if( !ok ) {
int m = n - 1 ;
for( int i = 0 ; i < g [x ].size();i ++ ) {
edge &e = edges [ g [x ][i ]];
if( e . cap > e . flow ) m = min(m , d [ e . to ]);
}
num [ d [x ]] -- ;
if( ! num [ d [x ]]) break;
d [x ] = m + 1 ;
num [ d [x ]] ++ ;
cur [x ] = 0 ;
if(x != s ) x = edges [ p [x ]]. from ;
}
}
return flow ;
}
}ISAP ;
int n , p , q ;
int s , t ;
int tot = 0 ;
int m ;
int main()
{
freopen( " data.txt " , " r " , stdin );
read(n );
s = n + 1 , t = s + 1 ;
ISAP .init(n * n , s , t );
for ( int i = 1 ; i <= n ; ++i ) {
int x ; read(x );
tot += x ;
ISAP .addegde(s , i , x );
}
for ( int i = 1 ; i <= n ; ++i ) {
int x ; read(x );
tot += x ;
ISAP .addegde(i , t , x );
}
read(m );
for ( int i = 1 ; i <= m ; ++i ) {
int k ;
read(k );
int suma = 0 , sumb = 0 ;
read(suma ); read(sumb );
tot += suma + sumb ;
ISAP .addegde(s , n + i + 2 , suma );
ISAP .addegde(n + i + m + 2 , t , sumb );
for ( int j = 1 ; j <= k ; ++j ) {
int x ;
read(x );
ISAP .addegde(n + 2 + i , x , inf );
ISAP .addegde(x , n + i + m + 2 , inf );
}
}
//cout << tot << " ! " << ISAP.maxflow() << endl;
int mincut = ISAP .maxflow();
printf( " %d \n " ,tot - mincut );
return 0 ;
}
京公网安备 11010502036488号