【小M的作物】

时间：2022-03-13 17:11:52

这是一道我好像没写过的最小割

这道题如果没有那\(m\)条限制，我们完全可以贪心来做

但是硬要用网络流怎么办

可以转化为最小割模型

我们将源点\(S\)表示为耕地\(A\)，汇点\(T\)表示为耕地\(B\)，对于一个点\(i\)，源点向\(i\)连一条容量为\(a_i\)的边，\(i\)向汇点连一条容量为\(b_i\)的边

这样的话为了使得\(S\)和\(T\)不连通，所以对于\(i\)来说\(a_i\)和\(b_i\)必须割掉一条，于是转化成了一个最小割

还有\(m\)条限制，我们可以把限制视为割掉某些边中的一条边，那么就必须额外割掉一条边

我们对于每一个限制搞一个虚点，先是\(S\)向虚点连一条容量为\(c\)的边，之后这个虚点向限制包含的所有点连为\(INF\)的边

这样话如果这点和\(S\)之间的边被割掉，说明后面那条和\(T\)相连的边没有被割掉，所以就必须割掉那条容量为\(c\)的边

耕地\(B\)同理

之后这道题还需要当前弧优化

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define re register

#define maxn 10005

#define INF 999999999

struct E

{

    int v,nxt,w,f;

}e[4400000];

int head[maxn],d[maxn],cur[maxn];

int n,num=1,S,T,ans,m,Now;

inline void add_edge(int x,int y,int z)

{

    e[++num].v=y;

    e[num].nxt=head[x];

    e[num].w=z;

    head[x]=num;

}

inline int min(int a,int b){return (a<b)?a:b;}

inline void connect(int x,int y,int z){add_edge(x,y,z),add_edge(y,x,0);}

inline int BFS()

{

    std::queue<int> q;

    for(re int i=0;i<=Now;i++)

    	d[i]=0,cur[i]=head[i];

    d[S]=1;

    q.push(S);

    while(!q.empty())

    {

        int k=q.front();

        q.pop();

        for(re int i=head[k];i;i=e[i].nxt)

        if(!d[e[i].v])

        {

            if(e[i].w<=e[i].f) continue;

            d[e[i].v]=d[k]+1;

            q.push(e[i].v);

        }

    }

    return d[T];

}

int dfs(int x,int now)

{

    if(x==T||!now) return now;

    int ff,flow=0;

    for(re int& i=cur[x];i;i=e[i].nxt)

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

    {

        ff=dfs(e[i].v,min(now,e[i].w-e[i].f));

        if(ff<=0) continue;

        flow+=ff,now-=ff;

        e[i].f+=ff,e[i^1].f-=ff;

        if(!now) break;

    }

    return flow;

}

inline int read()

{

    char c=getchar();

    int x=0;

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

    while(c>='0'&&c<='9')

      x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

int main()

{

    n=read();

    S=0,T=n+1;

    int a,b;

    for(re int i=1;i<=n;i++) a=read(),connect(S,i,a),ans+=a;

    for(re int i=1;i<=n;i++) b=read(),connect(i,T,b),ans+=b;

    m=read();

    Now=n+1;

    int N,c1,c2,t;

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

    {

        Now++,Now++;

        N=read(),c1=read(),c2=read();

        ans+=c1+c2;

        connect(S,Now-1,c1);

        connect(Now,T,c2);

        for(re int j=1;j<=N;j++)

        {

            t=read();

            connect(Now-1,t,INF);

            connect(t,Now,INF);

        }

    }

    while(BFS()) ans-=dfs(S,INF+1);

    std::cout<<ans;

    return 0;

}

/*

3

4 2 1

2 3 2

1

2 3 2 1 2

*/

相关文章