BZOJ 3438 小M的礼物

Description

小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子

有1个（就是可以种一棵作物）（用1...n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植

可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益

，小M找到了规则中共有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以

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

Input

第一行包括一个整数n

第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，

对于接下来的第i行：第一个整数ki，表示第i个作物组合中共有ki种作物，

接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。输出格式

Output

只有一行，包括一个整数，表示最大收益

Sample Input

3

4 2 1

2 3 2

2 3 2 1 2

Sample Output

11

样例解释A耕地种1，2，B耕地种3，收益4+2+3+2=11。

1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。

首先很明显的是网络流最小割。

考虑怎么建边；

从每个点向S连一条容量为$$a_i$$的边向T连一条容量为$$b_i$$的边表示这个点要么种在A菜地要么种在B菜地，两个只能选一个。

在考虑几个种在一起有加成的。

可以先新建一个节点（准确的说是两个），让他向那几个种在一起有加成的连inf的边，这样选的话就一定种在一起了。

之后跑一边最小割求出的是最小的失去的价值，用总的一减就是答案。

#include<iostream>

#include<queue>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int N = 2e6+10 , inf = 1e8;

inline int read()

{

    register int x = 0 , f = 0; register char c = getchar();

    while(c < '0' || c > '9') f |= c == '-' , c = getchar();

    while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();

    return f ? -x : x;

}

int n , cnt = 1 , tot , S , T;

int head[N] , d[N];

struct edge{ int v , nex , c; } e[N<<1];

inline void add(int u , int v , int c)

{

    e[++cnt].v = v; e[cnt].nex = head[u]; e[cnt].c = c; head[u] = cnt;

    e[++cnt].v = u; e[cnt].nex = head[v]; e[cnt].c = 0; head[v] = cnt;

    return ;

}

queue<int> q;

bool bfs()

{

    for(int i = 1 ; i <= tot ; ++i) d[i] = 0; q.push(S); d[S] = 1;

    while(q.size())

    {

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

        for(int i = head[x] , v ; i ; i = e[i].nex)

        {

            v = e[i].v; if(d[v] || e[i].c == 0) continue;

            d[v] = d[x] + 1; q.push(v);

        }

    }

    return d[T] != 0;

}

int dfs(int x , int flow)

{

    if(x == T || flow == 0) return flow;

    int k , res = 0;

    for(int i = head[x] , v ; i ; i = e[i].nex)

    {

        v = e[i].v;

        if(d[v] == d[x] + 1 && e[i].c)

        {

            k = dfs(v , min(flow , e[i].c));

            if(k)

            {

                e[i].c -= k; e[i^1].c += k; res += k; flow -= k;

                if(flow == 0) return res;

            }

            else d[v] = 0;

        }

    }

    return res;

}

int Dinic()

{

    int ans = 0;

    while(bfs()) ans += dfs(S , inf);

    return ans;

}

int main()

{

    n = read(); S = n + 1; T = tot = n + 2;

    int sum = 0 , x;

    for(int i = 1 ; i <= n ; ++i) x = read() , sum += x , add(S , i , x);

    for(int i = 1 ; i <= n ; ++i) x = read() , sum += x , add(i , T , x);

    int m = read() , y , k;

    while(m --)

    {

        k = read(); x = read(); y = read(); sum += x + y;

        add(S , ++tot , x); add(++tot , T , y);

        while(k--) x = read() , add(tot - 1 , x , inf) , add(x , tot , inf);

    }

//  cout << sum << endl;

    cout << sum - Dinic() << '\n';

    return 0;

}

巴特西

BZOJ 3438 小M的礼物

BZOJ 3438 小M的礼物

Description

Input

Output

最新文章

热门文章