BZOJ3438 小M的作物

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3438

这题觉得和上题有点类似吧。

如果没有联合在一起的收成，可以比较好做[我们将属于A的表示到s集中，属于B的表示到t集中]：

　　s往所有i连a[i]，所有i往t连b[i]。

这样的话，割集表示不选哪些，最后答案就是ans-最小割

现在考虑联合在一起的收成。

我们对于收成(wa,wb)，我们把它拆成两个点u,v，一个与s相连，边权为wa，另一个与t相连，边权为wb。

但是我们需要保证当我选择wa的收益时，需要将令所有关于它的点都不能放在t集合里；当我们选择wb的收益时，需要令所有关于它的点都不在s集合里。

那么怎么构图呢？

就将u往所有相关的i连一条INF的边，所有i往v连一条INF的边。

自从看了那篇有趣的博客，我觉得画图就应该这样画意识流...

这一题RE了很多次，原因就是数组开小了。

边集究竟有多大呢？以最坏的恶意，那么每个收益都是全体点的，那么就是m*n*2条边，然后每个点也要连出去两条，就是(m*n*2+n*2)*2=(2000000+2000)*2=4004000，然后总共的点数是n+2*m=3000个点。

以后要多想一想再来开数组啊....

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

inline int in(){

    int x=;char ch=getchar();

    while(ch>'' || ch<'') ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return x;

}

const int maxn=;

const int INF=0x3f3f3f3f;

struct Node{

    int data,next,low;

}node[];

#define now node[point].data

#define then node[point].next

#define www node[point].low

int n,m,cnt,ans;

int s,t,Idex;

int w1[maxn],w2[maxn];

int cur[maxn],head[maxn];

int dis[maxn],que[maxn];

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

    node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;

    node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=;head[v]=cnt++;

}

bool BFS(){

    memset(dis,-,sizeof(dis));

    int H=,T=;que[]=,dis[]=;

    while(H<T){

        H++;

        for(int point=head[que[H]];point!=-;point=then)

            if(www && dis[now]<){

                dis[now]=dis[que[H]]+;

                que[++T]=now;

            }

    }

    return dis[t]>;

}

int dfs(int x,int low){

    if(x==t) return low;

    int Low;

    for(int &point=cur[x];point!=-;point=then)

        if(www && dis[now]==dis[x]+){

            Low=dfs(now,min(low,www));

            if(Low){

                www-=Low,node[point^].low+=Low;

                return Low;

            }

        }

    return ;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("3438.in","r",stdin);

    freopen("3438.out","w",stdout);

#endif

    n=in();

    for(int i=;i<=n;i++) w1[i]=in(),ans+=w1[i];

    for(int i=;i<=n;i++) w2[i]=in(),ans+=w2[i];

    m=in();

    t=n+(m<<)+;

    for(int i=s;i<=t;i++) head[i]=-;

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

        add(s,i,w1[i]),add(i,t,w2[i]);

    Idex=n;

    int k,wa,wb,x;

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

        k=in(),wa=in(),wb=in();

        Idex++;add(s,Idex,wa);ans+=wa;

        Idex++;add(Idex,t,wb);ans+=wb;

        while(k--){

            x=in();

            add(Idex-,x,INF),add(x,Idex,INF);

        }

    }

    int flag;

    while(BFS()){

        for(int i=s;i<=t;i++) cur[i]=head[i];

        while(){

            flag=dfs(s,INF);

            if(!flag) break;

            ans-=flag;

        }

    }

    printf("%d",ans);

    return ;

}

巴特西

BZOJ3438 小M的作物

最新文章

热门文章