P1361小M的作物

发表于 更新于 分类于 本文字数： 386 阅读时长 ≈ 1 分钟

最小割，注意边e要估好，不然RE走起

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
const LL N = 5e3 + 86;
LL n, m; //n+1,n+2起始和终点，n+3以后虚点
struct edges
{
    int to, nxt,w;
} e[N*200];
int tot = 1, hd[N*100], cur[N*100];
void add(int x, int y, int v)
{
    e[++tot]=(edges){y,hd[x],v};hd[x]=tot;
}

int lv[N];
int bfs(int ss,int end)
{
    memset(lv,0,sizeof(lv));
    memcpy(cur, hd, sizeof(hd));
    queue<int> q;
    q.push(ss);
    lv[ss] = 1;
    while (!q.empty())
    {
        int p = q.front();
        //cout<<p<<":::"<<e[hd[p]].to<<":::"<<e[hd[p]].w<<"\n";
        q.pop();
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            //cout<<"##"<<to<<"::"<<vol<<"\n";
            if (vol>0&&!lv[to]){
                lv[to]=lv[p]+1;
                q.push(to);
            }
        }
    }
    //cout<<lv[end]<<"\n";
    return lv[end];
}

LL dfs(int p,int flow){
    if(p==n+2)
    return flow;
   LL r=flow;
    for(int eg=cur[p];eg&&r;eg=e[eg].nxt){
        cur[p]=eg;
        int to = e[eg].to, vol = e[eg].w;
        if(vol>0&&lv[to]==lv[p]+1){
            
            int c=dfs(to,min(vol*1ll,r));
            //cout<<p<<"::"<<to<<vol<<c<<"\n";
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //IN;OUT;
    cin >> n;
    LL s = 0;
    int x;
    f(i, 1, n)
    {
        cin >> x;
        s+=x;
        add(n + 1, i, x);
        add(i, n + 1, 0);
    }
    f(i,1,n){
        cin>>x;
        s+=x;
        add(i,n+2,x);
        add(n+2,i,0);
    }
    cin>>m;
    //cout<<"ook";
    f(i, 1, m)
    {
        int cn = n + 2 + 2 * i, k, te1, te2, ddd;
        cin >> k >> te1 >> te2;
        s+=(te1+te2);
        add(n + 1, cn - 1, te1);
        add(cn - 1, n + 1, 0);
        add(cn, n + 2, te2);
        add(n + 2, cn, 0);
        //cout<<i<<endl;
        f(i, 1, k)
        {
            cin >> ddd;
            add(cn - 1, ddd, 3e8);
            add(ddd, cn - 1, 0);
            add(ddd, cn, 3e8);
            add(cn, ddd, 0);
        }
    }
    LL ans=0;
    //cout<<"Ok"<<"\n";
    //return 0;
    while(bfs(n+1,n+2)){
        //cout<<ans;
        ans+=dfs(n+1,3e8);
    }
    cout<<s-ans;
    return 0;
}