AC日记——花店橱窗布置 codevs 1028

题目描述 Description

假设以最美观的方式布置花店的橱窗，有F束花，V个花瓶，我们用美学值（一个整数）表示每束花放入每个花瓶所产生的美学效果。为了取得最佳的美学效果，必须使花的摆放取得最大的美学值。

输入描述 Input Description

第一行为两个整数F,V(F<=V<=100)

接下来F行每行V个整数，第i行第j个数表示第i束花放入第j个花瓶的美学值。

输出描述 Output Description

一个整数，即最大美学值。

样例输入 Sample Input

2 2

10 0

5 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

思路：

　　费用流~~~；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define lit 10001

#define maxn 505

#define INF 0x7fffffff

using namespace std;

struct EdgeType {

    int v,e,f,w;

};

struct EdgeType edge[maxn*maxn];

int if_z,n,m,head[maxn],s,t=maxn-,cnt=;

int pre[maxn],ans,dis[maxn];

bool if_[maxn];

char Cget;

inline void in(int &now)

{

    now=,if_z=,Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

inline void edge_add(int u,int v,int w,int f)

{

    edge[++cnt].v=v,edge[cnt].f=f,edge[cnt].w=w,edge[cnt].e=head[u],head[u]=cnt;

    edge[++cnt].v=u,edge[cnt].f=,edge[cnt].w=-w,edge[cnt].e=head[v],head[v]=cnt;

}

bool spfa()

{

    int que[maxn*maxn],h=,tail=;

    for(int i=s;i<=t;i++) dis[i]=INF,pre[i]=-;

    dis[s]=,que[]=s,if_[s]=true;

    while(h<tail)

    {

        int now=que[h++];

        for(int i=head[now];i;i=edge[i].e)

        {

            if(dis[edge[i].v]>dis[now]+edge[i].w&&edge[i].f>)

            {

                pre[edge[i].v]=i;

                dis[edge[i].v]=dis[now]+edge[i].w;

                if(!if_[edge[i].v])

                {

                    if_[edge[i].v]=true;

                    que[tail++]=edge[i].v;

                }

            }

        }

        if_[now]=false;

    }

    return dis[t]<INF;

}

int main()

{

    in(n),in(m);int w;

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

    {

        edge_add(s,i,,);

        for(int j=;j<=m;j++)

        {

            in(w);

            edge_add(i,j+n,lit-w,);

        }

    }

    for(int i=;i<=m;i++) edge_add(i+n,t,,);

    while(spfa())

    {

        int now=t;

        while(pre[now]!=-)

        {

            edge[pre[now]].f-=;

            edge[pre[now]^].f+=;

            now=edge[pre[now]^].v;

        }

        ans+=lit-dis[t];

    }

    cout<<ans;

    return ;

}

巴特西

AC日记——花店橱窗布置 codevs 1028

最新文章

热门文章