洛谷 P1361 小M的作物 题解【网络流】【最小割】

作者: wjyyy 分类: 最小割,构造,网络流,解题报告 发布时间: 2018-06-28 21:05

点击量:5

 

   最小割建模真的是毒瘤啊。。。

 

题目描述

小M在MC里开辟了两块巨大的耕地A和B(你可以认为容量是无穷),现在,小P有n中作物的种子,每种作物的种子有1个(就是可以种一棵作物)(用1…n编号)。

 

现在,第i种作物种植在A中种植可以获得ai的收益,在B中种植可以获得bi的收益,而且,现在还有这么一种神奇的现象,就是某些作物共同种在一块耕地中可以获得额外的收益,小M找到了规则中共有m种作物组合,第i个组合中的作物共同种在A中可以获得c1i的额外收益,共同总在B中可以获得c2i的额外收益。

 

小M很快的算出了种植的最大收益,但是他想要考考你,你能回答他这个问题么?

 

输入输出格式

输入格式:

第一行包括一个整数n

 

第二行包括n个整数,表示ai第三行包括n个整数,表示bi第四行包括一个整数m。

 

接下来m行:对于接下来的第i行:第一个整数ki,表示第i个作物组合中共有ki种作物,

 

接下来两个整数c1i,c2i,接下来ki个整数,表示该组合中的作物编号。

 

输出格式:

只有一行,包括一个整数,表示最大收益

 

输入输出样例

输入样例#1:
3
4 2 1
2 3 2
1
2 3 2 1 2
输出样例#1:
11

说明

样例解释

A耕地种1,2,B耕地种3,收益4+2+3+2=11。

 

数据范围与约定

1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。

 

   类似善意的投票,都像是把物品分到两个部分,要求损失最小,这种情况一般都是最小割的二者取一式问题。那么这个题建模不像别的题那么容易,因为附加条件是m种组合给出额外收益。

 

   如果直接向最小割上套,组合有交集,肯定不可能直接求解,但是我们可以试试其他思路。题目要求只要组合中的任何一个不在同一边,就不产生额外收益。那么我们想办法表示出这种情况,至少要从组合给各个点连一条边,同时满足断掉任意一条后,组合的源边失效。这个模型慢慢套最小割,可以找出一种方案(其实也没有定向的思路),就是把A点向组合i连接权值为c1[i]的边,组合i向其中的物品连接权值为∞的边,并把A点分别向各种物品i连接权值为a[i]的边,B点同理。这样一旦某条边成为最小割,那么它所属的集合也一定在最小割上(可以多试试,是成立的)

 

   于是最小割求的就是最小损失了,把理想收益\(\sum_{i=1}^n(ai+bi)+\sum_{i=1}^m(c1i+c2i)\)减掉最小损失就是实际收益。

 

   最小割建模过程见多了应该就熟练了。

Code:(这个题常数过大过不了 于是顺便学了isap)

#include<cstring>
#include<cstdio>
#include<queue>
#define A 0
#define B 3008
#define inf 0x3fffffff
using std::queue;
struct node
{
    int n,v;
    node *nxt,*op;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
        op=NULL;
    }
    node()
    {
        nxt=NULL;
        op=NULL;
    }
};
node head[4444],*tail[4444];
void add(int from,int to,int v)
{
    tail[from]->nxt=new node(to,v);
    tail[from]=tail[from]->nxt;
    tail[to]->nxt=new node(from,0);
    tail[to]=tail[to]->nxt;
    tail[from]->op=tail[to];
    tail[to]->op=tail[from];
}
bool used[4444];
int sum=0;
node *pre[4444],*pro[4444];
int d[4444];
int gap[4444];
void bfs()
{
    memset(gap,0,sizeof(gap));
    queue<int> q;
    q.push(B);
    d[B]=1;
    gap[1]=1;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        node *p=&head[k];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(d[p->n])
                continue;
            d[p->n]=d[k]+1;
            gap[d[p->n]]++;
            q.push(p->n);
        }
    }
}
 
void isap()
{
    int s=A;
    for(int i=0;i<=3050;i++)
        pro[i]=&head[i];
    gap[0]=3050;
    while(d[A]!=B)
    {
        if(s==B)
        {
            int minn=inf;
            node *p=pre[B];
            while(p!=NULL)
            {
                minn=minn<p->v?minn:p->v;
                p=pre[p->op->n];
            }
            sum+=minn;
            p=pre[B];
            while(p!=NULL)
            {
                p->v-=minn;
                p->op->v+=minn;
                p=pre[p->op->n];
            }
            s=A;
            continue;
        }
        int flag=0;
        node *p=pro[s];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(p->v&&d[p->n]+1==d[s])
            {
                flag=1;
                pre[p->n]=p;
                pro[s]=p;
                s=p->n;
                break;
            }
        }
        if(flag==0)//返回
        {
            node *p=&head[s];
            int r=B;
            while(p->nxt!=NULL)
            {
                p=p->nxt;
                if(p->v)
                    r=r<d[p->n]+1?r:d[p->n]+1;
            }
            gap[d[s]]--;
            gap[r]++;
            if(gap[d[s]]==0)
                return;
            d[s]=r;
            pro[s]=&head[s];
            if(s!=A)
                s=pre[s]->op->n;
        }
    }
}
int main()
{
    int n,u,ans=0;
    scanf("%d",&n);
    for(int i=0;i<=3050;i++)//源点为0,汇点为3008
        tail[i]=&head[i];
    for(int i=1;i<=n;i++)//作物为1~n
    {
        scanf("%d",&u);
        add(A,i,u);
        ans+=u;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u);
        add(i,B,u);
        ans+=u;
    }
    int m,k,v,w;
    scanf("%d",&m);
    bool h=false;
    while(m--)//组合为1001~1000+m和2001~2000+
    {
        h=true;
        scanf("%d",&k);
        scanf("%d%d",&u,&v);
        ans+=u+v;
        add(A,1001+m,u);
        add(2001+m,B,v);
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&w);
            add(1001+m,w,inf);
            add(w,2001+m,inf);
        }
    }
    isap();
    printf("%d\n",ans-sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */