luogu P1361 小M的作物

题目链接

题解

源汇点为A,B

向种子连边,容量为价值,每个种子能与A或B联通,考虑最小割

用建边的总流量减去最小割就是答案

相同利益的时候新建节点,由额外利益构成群体向新建节点连边容量INF,新建节点向对应(源\汇)连对应额外利益的边

开始只新开了一个节点连了个双向边orz

代码

// luogu-judger-enable-o2

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::queue;

using std::min;

#define INF 0x7fffffff

const int maxn = 770000;

inline int read() {

    int x=0;char c=getchar();

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

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();

    return x;

}

int n,S,T,sum,A[maxn],B[maxn];

struct node{

    int v,flow,next;

}edge[maxn];int head[maxn],num=1;

inline void add_edge(int u,int v,int flow) {

    edge[++num].v=v;edge[num].flow=flow,edge[num].next=head[u];head[u]=num;

    edge[++num].v=u;edge[num].flow=0;edge[num].next=head[v];head[v]=num;

}

int cur[maxn],lev[maxn];

bool spfa() {

    memset(lev,-1,sizeof lev);

    memcpy(cur,head,sizeof head);

    queue<int>que;

    que.push(S);lev[S]=0;

    while(!que.empty()) {

        int u=que.front();que.pop();

        for(int i=head[u];i;i=edge[i].next) {

            int v=edge[i].v;

            if(edge[i].flow>0&&lev[v]<0) {

                lev[v]=lev[u]+1;que.push(v);

            }

        }

    }

    if(lev[T]!=-1)return true;

    else return false;

}

int dfs(int now,int flow) {

    if(now==T)return flow;

    int rest=0,delta;

    for(int &i=cur[now];i;i=edge[i].next) {

        int v=edge[i].v;

        if(lev[v]==lev[now]+1&&edge[i].flow>0) {

            delta=dfs(v,min(flow-rest,edge[i].flow));

            if(delta) {

                edge[i].flow-=delta;

                edge[i^1].flow+=delta;

                rest+=delta;if(rest==flow)break;

            }

        }

    }

    if(rest==flow)lev[now]=-1;

    return rest;

}

int ans=0;

void dinic() {

    while(spfa())

         ans-=dfs(S,INF);

}

int main() {

    n=read();

    S=0,T=n+1;

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

        add_edge(S,i,A[i]=read()),ans+=A[i];

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

        add_edge(i,T,B[i]=read()),ans+=B[i];

    int m=read();

    for(int k,c1,c2,i=1;i<=m;++i) {

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

        for(int a,j=1;j<=k;++j)

            add_edge(a=read(),T+i+m,INF),add_edge(T+i,a,INF);

        add_edge(S,T+i,c1),add_edge(T+i+m,T,c2);

        ans+=c1+c2;

    }

    dinic();

    printf("%d\n",ans);

    return 0;

}

巴特西

luogu P1361 小M的作物

题目链接

题解

代码

最新文章

热门文章