[Luogu1361]小M的作物

Posted on | In

最近学习网络流，感觉代码都巨长

网络流的题目无非都是一个套路

就是首先建模，然后随便套套模板

但是这题显然没有这么简单

一开始各种乱想，反正没想到最小割

然后随手点了一发题解，借鉴学习一下大神的思路

然后就TM恍然大悟，原来就是求最小割

最小割 $=$ 最大流

按照大神的思路，把$A$田地当做源点

$B$田地当做汇点，把$n$种植物当做中间点

没有最大收益的时候就直接连接源点、汇点和中间点

加上最大收益后，有些点就像是被捆绑在了一起

我们可以在这$m$个点集和源点、汇点之间，

再设置$2m$个中间点，把这些点和源点、汇点和中间点连接在一起

最大流量就是增加的收益

听起来真的很绕，但是真的是这样

题目要求最大收益，其实就是总收益 $-$ 最小割

剩下的部分，似乎直接上模板就差不多了

然而我$TM$直接$TLE$直接飞起

这题好像要优化一点点，至少朴素的$Dinic$模板不行

又是一位大神告诉我一个玄学优化

真$TM$一手骚操作，瞬间就切掉

这个不是我的东西我就先不讲了哈

自我感觉码风美好

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
111
#include<bits/stdc++.h>
#define INF 99999999
using namespace std;
struct XM
{
    int to;
    int dis;
    int from;
}
edge[4000004];
int cur[40004];
int deep[40004];
int head[40004];
int m,n,s,k,t,x,y,z,ans,num=-1;
inline void add(int from,int to,int dis)
{
    edge[++num].from=head[from];
    edge[num].to=to;
    edge[num].dis=dis;
    head[from]=num;
}
inline bool Bfs()
{
    memset(deep,0,sizeof(deep));
    queue < int > Q;
    while(!Q.empty()) Q.pop();
    Q.push(s);deep[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(register int i=head[u];i!=-1;i=edge[i].from)
        {
            int v=edge[i].to;
            if(deep[v]==0&&edge[i].dis>0)
            {
                deep[v]=deep[u]+1;
                Q.push(v);
            }

        }
    }
    if(deep[t]!=0) return true;
    else return false;
}
inline int Dfs(int u,int f)
{
    if(u==t) return f;
    int sum=0;
    for(register int &i=cur[u];i!=-1;i=edge[i].from)
    {
        int v=edge[i].to;
        if(deep[v]==deep[u]+1&&edge[i].dis>0)
        {
            int d=Dfs(v,min(f,edge[i].dis));
            if(d>0)
            {	
            	sum+=d;f-=d;
                edge[i].dis-=d;
                edge[i^1].dis+=d;
                if(!f) break;
            }
        }
    }
    return sum;
}
int main()
{
    scanf("%d",&n);
    s=n+1;t=s+1;
    memset(head,-1,sizeof(head));
    for(register int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        ans+=x;
        add(s,i,x);
        add(i,s,0);
    }
    for(register int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        ans+=x;
        add(i,t,x);
        add(t,i,0);
    }
    scanf("%d",&m);
    for(register int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&k,&x,&y);
        ans+=x;ans+=y;
        add(s,n+i+2,x);
        add(n+i+2,s,0);
        add(n+m+i+2,t,y);
        add(t,n+m+i+2,0);
        for(register int j=1;j<=k;++j)
        {
            scanf("%d",&z);
            add(n+i+2,z,INF);
            add(z,n+i+2,0);
            add(z,n+m+i+2,INF);
            add(n+m+i+2,z,0);
        }
    }
    while(Bfs())
    {
    	memcpy(cur,head,sizeof(cur));
    	ans-=Dfs(s,INF);
    }
    printf("%d\n",ans);
    return 0;
}