Mike的农场 BZOJ4177

分析：

最小割，不选则割的建模题...（然而一开始我当成了费用流，简直丧心病狂...最后想到了最小割...）

对于条件一，直接建一条双向边就可以了，并且不计入sum中，因为这是作为费用的存在，让它跑出来就可以了，不要考虑太多的。对于条件二，建一个点，分别连向{S}牧场，流量为inf，并且如果是0的话，连接S，如果是1的话，连接T。

附上代码：

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <iostream>

#include <queue>

#include <cstdlib>

using namespace std;

#define N 15005

#define S 0

#define T 15001

int head[N],cnt,dep[N],n,m,k;long long sum;

struct node

{

    int to,next,val;

}e[1000010];

void add(int x,int y,int z){e[cnt].to=y;e[cnt].next=head[x];e[cnt].val=z;head[x]=cnt++;}

void insert(int x,int y,int z){add(x,y,z);add(y,x,0);}

int bfs()

{

    memset(dep,-1,sizeof(dep));

    queue <int>q;while(!q.empty())q.pop();q.push(S);dep[S]=1;

    while(!q.empty())

    {

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

        for(int i=head[x];i!=-1;i=e[i].next)

        {

            int to1=e[i].to;

            if(dep[to1]==-1&&e[i].val)dep[to1]=dep[x]+1,q.push(to1);

        }

    }

    return dep[T]==-1?0:1;

}

int dfs(int x,int maxf)

{

    if(x==T)return maxf;

    int tflow=maxf,nowf;

    for(int i=head[x];i!=-1;i=e[i].next)

    {

        int to1=e[i].to;

        if(dep[to1]==dep[x]+1&&e[i].val)

        {

            nowf=dfs(to1,min(e[i].val,tflow));

            if(!nowf)dep[to1]=-1;

            tflow-=nowf,e[i].val-=nowf,e[i^1].val+=nowf;

            if(!tflow)break;

        }

    }

    return maxf-tflow;

}

int main()

{

    memset(head,-1,sizeof(head));

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;i++)

    {

        int x;

        scanf("%d",&x);sum+=x;

        insert(S,i,x);

    }

    for(int i=1;i<=n;i++)

    {

        int x;

        scanf("%d",&x);sum+=x;

        insert(i,T,x);

    }

    for(int i=1;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        insert(x,y,z);insert(y,x,z);

    }

    for(int i=1;i<=k;i++)

    {

        int x,y,z,v;scanf("%d%d%d",&x,&y,&z);sum+=z;

        if(y==0)

        {

            insert(S,i+n,z);

            while(x--){scanf("%d",&v);insert(i+n,v,1<<30);}

        }else

        {

            insert(i+n,T,z);

            while(x--){scanf("%d",&v);insert(v,i+n,1<<30);}

        }

    }

    long long ans=0;

    while(bfs())ans+=dfs(S,1<<30);

    printf("%lld\n",sum-ans);

    return 0;

}