题解 P1361 【小M的作物】

· · 题解

题意

给定一些物品，可以放在A或B中，取得不同收益。 某些物品同时放在A或B中，可以获得额外收益。 求收益的最大值。

题解

看到二者选其一，我们不禁联想到了最小割模型

很明显，这道题主要的问题在于建模。若是不考虑额外收益，图是很容易建出来的 ：

这样的图，要使其不连通，每个点都不能同时连接源点S和汇点T，也就是说，保证其只属于一个集合

这时跑一遍最小割，是删去的最小，留下的就是最大的了 假装不能直接取最大值

但是现在加入了额外收益，应该如何改进上述的图呢？

通过对题意的了解，我们知道：

  1. 如果割掉了1、2，那么把边权为c_{1}的边也要割掉
  2. 如果割掉了3、4，那么把边权为c_{2}的边也要割掉
  3. 如果割掉了1、4或者2、3，那么两条边都要割掉

此时，我们已经大致想到此图的构图方法了。由1、2我们了解到，c_1\ \ c_2应该分别与1\text{、}2，3\text{、}4并联 电学乱入，于是我们瞎搞思考出了下图：

其中\color{SkyBlue}{\text{蓝色}} 的边边权是+\infty，是不能删除的

我们发现，此图非常符合题目的限制。于是我们建个图套个板子就A了

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
namespace in{
    char buf[1<<21],*p1=buf,*p2=buf;
    inline int getc(){
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
    }
    template <typename T>inline void read(T& t){
        t=0;int f=0;char ch=getc();
        while (!isdigit(ch)){
            if(ch=='-')f = 1;
            ch=getc();
        }
        while(isdigit(ch)){
            t=t*10+ch-48;
            ch = getc();
        }
        if(f)t=-t;
    }
    template <typename T,typename... Args> inline void read(T& t, Args&... args){
        read(t);read(args...);
    }
}
namespace out{
    char buffer[1<<21];
    int p1=-1;
    const int p2 = (1<<21)-1;
    inline void flush() {
        fwrite(buffer,1,p1+1,stdout),
        p1=-1;
    }
    inline void putc(const char &x) {
        if(p1==p2)flush();
        buffer[++p1]=x;
    }
    template <typename T>void write(T x) {
        static char buf[15];
        static int len=-1;
        if(x>=0){
            do{
                buf[++len]=x%10+48,x/=10;
            }while (x);
        }else{
            putc('-');
            do {
                buf[++len]=-(x%10)+48,x/=10;
            }while(x);
        }
        while (len>=0)
            putc(buf[len]),--len;
    }
}
using namespace std;
const int maxn=40010,maxe=1000010*2;
struct Graph{
    struct node{
        int v,w,nxt;
    }e[maxe<<1];
    int head[maxn],cur[maxn],tot;
    int dis[maxn];
    int s,t;
    void init(int _s,int _t){s=_s,t=_t;tot=1;memset(head,0,sizeof head);}
    Graph(int _s=0,int _t=0){init(_s,_t);}
    void add(int u,int v,int w){
        //printf("%d %d %d\n",u,v,w);
        e[++tot]=(node){v,w,head[u]},head[u]=tot;
        e[++tot]=(node){u,0,head[v]},head[v]=tot;
    }
    #define v e[i].v
    inline bool bfs(){
        queue<int>q;
        memset(dis,0,sizeof dis);
        memcpy(cur,head,sizeof head);
        dis[s]=1;q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt)
                if(!dis[v]&&e[i].w){
                    dis[v]=dis[u]+1,q.push(v);
                    if(v==t)return true;
                }
        }
        return  false;
    }
    int dfs(int u,int flow){
        if(u==t)return flow;
        int rest=flow;
        for(int i=cur[u];i&&rest;i=e[i].nxt){
            if(dis[v]==dis[u]+1&&e[i].w){
                int tmp=dfs(v,min(rest,e[i].w));
                rest-=tmp,e[i].w-=tmp,e[i^1].w+=tmp;
            }
            cur[u]=i;
        }
        if(rest==0)dis[u]=-1;
        return flow-rest;
    }
    #undef v
    int dinic(){
        int ans=0;
        while(bfs())
            while(int sth=dfs(s,2e9))
                ans+=sth;
        return ans;
    }
}G;
int n,m,c[1000],tot;
int sum=0;
signed main(){
    //freopen("1.in","r",stdin);
    G.init(1000+1000*4+100,1000+1000*4+101); 
    in::read(n);tot=n;
    for(int i=1;i<=n;i++){
        int tmp;in::read(tmp);
        G.add(G.s,i,tmp);
        sum+=tmp;
    }
    for(int i=1;i<=n;i++){
        int tmp;in::read(tmp);
        G.add(i,G.t,tmp);
        sum+=tmp;
    }
    in::read(m);
    for(int i=1;i<=m;i++){
        int k,c1,c2,tmp;
        in::read(k,c1,c2);
        G.add(G.s,tot+1,c1);
        G.add(tot+2,G.t,c2);
        sum+=c1+c2;
        for(int j=1;j<=k;j++){
            in::read(tmp);
            G.add(tot+1,tmp,2e9);
            G.add(tmp,tot+2,2e9);
        }
        tot+=2;
    }
    out::write(sum-G.dinic());
    out::flush();
    return 0;
}