正解:网络流

解题报告:

传送门!

我网络流的基础题都还麻油做完就来做这个了,,,wsl,,,

首先想下最基础的构图方法

不难想到把猪圈和顾客分别当做节点,然后新建一个源点和汇点

然后考虑怎么连边,首先肯定要

源点向初始猪圈连权值为猪圈内猪的个数的边

顾客向汇点连权值为购买上限的边

猪圈向顾客连权值为inf的边

然后关键就是怎么表示出来猪圈之间是可以相互调配的昂QAQ

然后就考虑把每个猪圈拆成n个点,表示这n轮,然后表示起来就很简单了昂

相同的猪圈之间连inf的边

同一轮打开的猪圈之间连inf的边

但是这时候发现,边太多了,会T,考虑要么转变建图方式要么优化

先看优化趴

那首先可以想到最后一轮麻油打开的猪圈可以删了,显然它们是不会有贡献了的

然后如果有几个点的来源是相同的,显然它们可以缩成一个点的

如果有几个点的去向是相同的,显然也是可以缩成一个点的

如果从u到v的流量是inf而且v除了u麻油别的流量来源了同样也是能缩成一个点的

然后仔细梳理一下,发现如果按照这些原则,其实就相当于是有了个新的建图方式,下面大概港下规则

首先每个顾客是一个节点不变

然后对每个猪圈的第一个顾客,由源点向它连权值为最初这个猪圈中猪的个数的边,如果有很多条就合并成一条就好

然后对每个猪圈的所有顾客,按顺序从前一个连向后一个

最后从每个顾客向汇点连权值为购买上限的边就好

这样子建图就能保证,只有O(N)级别的点的个数,就欧克了QAQ

而且其实这样子建图也是可以用思路正常解释出来的QAQ

大概就是,可以把每个人看做一个调度站,就是说他能调度一部分猪圈里猪的数量,当下一个人需要的时候就分一些给下一个人就好,不知道讲清楚麻油,,,意会着理解下QAQ?

最后总结一下,对这种网络流的问题,如果实在麻油什么很优秀的想法的时候,可以先考虑暴力建图,然后再慢慢考虑优化,再想到更好的建图思路

over!

最后关于那个,我说的建图过程,其实是有点儿难建的,,,?我我我我想不到什么好方法就直接瞎搞了,就开了个数组,用了点儿链表的思想暴力存QAQ

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define ri rg int

#define rc rg char

#define rb rg bool

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define rp(i,x,y) for(rg int i=x;i<=y;++i)

#define my(i,y,x) for(rg int i=x;i>=y;--i)

#define e(i,x) for(rg int i=head[x];i!=-1;i=edge[i].nxt)

const int N=+,M=+,inf=1e8;

int n,m,a[M],nw_to[M],ed_cnt=-,flow,head[N],dep[N],st,to;

struct ed{int to,nxt,wei;}edge[(N<<)*];

queue<int>Q;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri x,ri y,ri z){edge[++ed_cnt]=(ed){y,head[x],z};head[x]=ed_cnt;}

il bool bfs()

{

    Q.push(st);memset(dep,,sizeof(dep));dep[st]=;

    while(!Q.empty())

    {

        ri nw=Q.front();Q.pop();

        e(i,nw)if(!dep[t(i)] && w(i))Q.push(t(i)),dep[t(i)]=dep[nw]+;

    }

    return dep[to];

}

il int dfs(ri nw,ri f)

{

    if(nw==to || !f)return f;ri ret=,tmp;

    e(i,nw)if(dep[t(i)]==dep[nw]+ && w(i))if(tmp=dfs(t(i),min(f,w(i))))f-=tmp,ret+=tmp,w(i)-=tmp,w(i^)+=tmp;

    return ret;

}

il int dinic(){while(bfs())flow+=dfs(st,inf);return flow;}

int main()

{

//    freopen("1.in","r",stdin);freopen("pig.out","w",stdout);

    m=read();n=read();rp(i,,m)a[i]=read();st=n+;to=n+;memset(head,-,sizeof(head));

    rp(i,,n)

    {

        ri num=read(),wei=;

        while(num--)

        {

            ri tmp=read();

            if(!nw_to[tmp])wei+=a[tmp],nw_to[tmp]=i;

            else ad(nw_to[tmp],i,inf),ad(i,nw_to[tmp],),nw_to[tmp]=i;

        }

        num=read();ad(i,to,num);ad(to,i,);if(wei)ad(st,i,wei),ad(i,st,);

    }

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

    return ;

}

这儿是代码QAQ

巴特西

BZOJ1280 Emmy卖猪pigs 网络流

正解:网络流

解题报告:

最新文章

热门文章