codevs 1028 花店橱窗布置

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 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

二分图

km或费用流

本蒟蒻用的费用流机房某z姓大佬好像在学km 先模几发%%%

屠龙宝刀点击就送

#include <cstdio>

#include <queue>

#define N 1000005

#define FWQ 0xefefefef

using namespace std;

struct Edge

{

    int next,flow,cost,to;

}edge[N<<];

bool vis[N];

int head[N],cnt=,F,V,fa[N],dis[N];

void ins(int u,int v,int w,int l)

{

    edge[++cnt].next=head[u];

    edge[cnt].to=v;

    edge[cnt].flow=w;

    edge[cnt].cost=l;

    head[u]=cnt;

}

bool spfa(int s,int t)

{

    queue<int>q;

    for(int i=s;i<=t;++i) vis[i]=,dis[i]=FWQ;

    dis[s]=;

    q.push(s);

    for(int now;!q.empty();)

    {

        now=q.front();

        q.pop();

        vis[now]=;

        for(int u=head[now];u;u=edge[u].next)

        {

            int v=edge[u].to;

            if(dis[v]<dis[now]+edge[u].cost&&edge[u].flow)

            {

                dis[v]=dis[now]+edge[u].cost;

                fa[v]=u;

                if(!vis[v])

                {

                    vis[v]=;

                    q.push(v);

                }

            }

        }

    }

    return dis[t]!=FWQ;

}

int dinic(int s,int t)

{

    int ans=;

    for(;spfa(s,t);)

    {

        for(int i=t;i!=s&&i;i=edge[fa[i]^].to)

        {

            edge[fa[i]].flow--;

            edge[fa[i]^].flow++;

        }

        ans+=dis[t];

    }

    return ans;

}

int Main()

{

    scanf("%d%d",&F,&V);

    int s=,t=F+V+;

    for(int i=;i<=F;++i) ins(s,i,,),ins(i,s,,);

    for(int i=F+;i<=F+V;++i) ins(i,t,,),ins(t,i,,);

    for(int a,i=;i<=F;++i)

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

      scanf("%d",&a),ins(i,j+F,,a),ins(j+F,i,,-a);

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

    return ;

}

int sb=Main();

int main(int argc,char *argv[]){;}