[P1361] 小M的作物

没想到今天早上的第一题网络流就血了这么多发
从经典的二选一问题上魔改仍然考虑最小割
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 163840, MAXN = 2602144;

#define reset(x) memset(x,0,sizeof x)

namespace solver {

struct graph {

    int n,m,M,S,T,head[N],cur[N],dep[N],gap[N],q[N];

    long long ans;

    struct ed {

        int to,nxt,val;

    } edge[MAXN];

    void init(int n0,int m0,int S0,int T0) {

        n=n0,m=m0,S=S0,T=T0,M=1,reset(gap);

        reset(head),reset(cur),reset(dep),reset(q);

    }

    void make(int u,int v,int w) {

        edge[++M]=(ed) {v,head[u],w},head[u]=M;

    }

    int dfs(int u,int mx) {

        if (u==T)

            return mx;

        int num=0,f;

        for (int &i=cur[u],v; i; i=edge[i].nxt)

            if (dep[v=edge[i].to]==dep[u]-1 && (f=edge[i].val))

                if (edge[i].val-=(f=dfs(v,min(mx-num,f))), edge[i^1].val+=f, (num+=f)==mx)

                    return num;

        if (!--gap[dep[u]++])

            dep[S]=n+1;

        return ++gap[dep[u]],cur[u]=head[u],num;

    }

    void solve() {

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

            cur[i]=head[i];

        ans=0;

        for (gap[0]=n; dep[S]<=n; ans+=dfs(S,0x7fffffff));

    }

} g;

int n,m,S,T,t1,t2,t3;

void init() {

    g.init(n,m,S,T);

}

int solve() {

    g.solve();

    return g.ans;

}

void make(int t1,int t2,int t3) {

    g.make(t1,t2,t3);

    g.make(t2,t1,0);

}

} // namespace solver

int n,a[10005],b[10005],m,c[10005][2];

signed main() {

    int ans = 0;

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i], ans+=a[i];

    for(int i=1;i<=n;i++) cin>>b[i], ans+=b[i];

    cin>>m;

    solver::n = n+m*2+2;

    solver::S = n+m*2+1;

    solver::T = n+m*2+2;

    solver::init();

    for(int i=1;i<=n;i++) solver::make(n+m*2+1, i, a[i]);

    for(int i=1;i<=n;i++) solver::make(i, n+m*2+2, b[i]);

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

        int k;

        cin>>k>>c[i][0]>>c[i][1];

        ans += c[i][0] + c[i][1];

        solver::make(n+m*2+1, n+i*2-1, c[i][0]);

        solver::make(n+i*2, n+m*2+2, c[i][1]);

        while(k--) {

            int tmp;

            cin>>tmp;

            solver::make(n+i*2-1,tmp,2e9+10);

            solver::make(tmp,n+i*2,2e9+10);

        }

    }

    cout<<ans - solver::solve()<<endl;

}
巴特西

[P1361] 小M的作物 - 最小割

最新文章

热门文章
