1028 花店橱窗布置

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

12

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

二分图匹配 图论

题解:

模板:匈牙利算法的升级版--KM算法

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
const int inf=0x3f3f3f3f;
int n,m,ans,match[N],w[N][N],d;
int fx[N],fy[N],lx[N],ly[N];
bool dfs(int u){
    fx[u]=1;
    for(int i=1;i<=m;i++){
        if(!fy[i]&&lx[u]+ly[i]==w[u][i]){
            fy[i]=1;
            if(!match[i]||dfs(match[i])){
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
void KM(){
    for(int i=1;i<=n;i++){
        lx[i]=-inf;
        for(int j=1;j<=m;j++) lx[i]=max(lx[i],w[i][j]);
    }
    for(int i=1;i<=n;i++){
        for(;;){
            memset(fx,0,sizeof fx);
            memset(fy,0,sizeof fy);
            if(dfs(i)) break;
            d=inf;
            for(int j=1;j<=n;j++){
                for(int k=1;k<=m;k++){
                    if(fx[j]&&!fy[k]){
                        d=min(d,lx[j]+ly[k]-w[j][k]);
                    }
                }
            }
            if(d==inf) break;
            for(int j=1;j<=n;j++) if(fx[j])lx[j]-=d;
            for(int j=1;j<=m;j++) if(fy[j])ly[j]+=d;
        }
    }
    for(int i=1;i<=m;i++) if(match[i]) ans+=w[match[i]][i];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&w[i][j]);
        }
    }
    KM();
    printf("%d",ans);
    return 0;
}
时间: 10-04

1028 花店橱窗布置的相关文章

codevs 1028 花店橱窗布置 (KM)

/*裸地KM*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 110 #define inf 0x3f3f3f3f using namespace std; int n,m,ans,match[maxn],w[maxn][maxn],d; int fx[maxn],fy[maxn],lx[maxn],ly[maxn]; bool Dfs(int i) { fx[i]=1; for(

codevs 1028 花店橱窗布置

最大费用最大流.分为两个集合,流量为1,费用为给的值即可. #include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#define maxv 202#define maxe 20005#define inf 12345678using namespace std;int ff,vv,g[maxv],prev[maxv],pree[maxv],

RQNOJ PID496/[IOI1999]花店橱窗布置

PID496 / [IOI1999]花店橱窗布置 ☆ 题目描述 某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按1到V顺序 编号,V是花瓶的数目.花束可以移动,并且每束花用1到F的整数标识.如果I < J,则花束I必须放在花束J左边的花瓶中.例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有花束在放入花瓶时必须保持其标识 数的顺序,即杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中.如果

P1854 花店橱窗布置

P1854 花店橱窗布置 题目描述 某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按1到V顺序编号,V是花瓶的数目.花束可以移动,并且每束花用1到F的整数标识.如果I < J,则花束I必须放在花束J左边的花瓶中.例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有花束在放入花瓶时必须保持其标识数的顺序,即杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中.如果花瓶的数目大于花束的数目,则多余

codevs1028花店橱窗布置(费用流)

这几天刚学了费用流,找到了这道题来练一练手. 题目: 题目描述 Description 假设以最美观的方式布置花店的橱窗,有F束花,V个花瓶,我们用美学值(一个整数)表示每束花放入每个花瓶所产生的美学效果.为了取得最佳的美学效果,必须使花的摆放取得最大的美学值. 输入描述 Input Description 第一行为两个整数F,V(F<=V<=100) 接下来F行每行V个整数,第i行第j个数表示第i束花放入第j个花瓶的美学值. 输出描述 Output Description 一个整数,即最大美

洛谷 P1854 花店橱窗布置

题目描述 某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按1到V顺序编号,V是花瓶的数目.花束可以移动,并且每束花用1到F的整数标识.如果I < J,则花束I必须放在花束J左边的花瓶中.例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有花束在放入花瓶时必须保持其标识数的顺序,即杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中.如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶只

luogu P1854 花店橱窗布置

题目描述 某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按1到V顺序编号,V是花瓶的数目.花束可以移动,并且每束花用1到F的整数标识.如果I < J,则花束I必须放在花束J左边的花瓶中.例如,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有花束在放入花瓶时必须保持其标识数的顺序,即杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中.如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶只

【Luogu】P1854花店橱窗布置(DP)

照例良心题目链接 此题使用f[i][j]表示前i束花放进前j个花瓶的时候的最大值.转移方程如下 f[i][j]=max(f[i][j-1],f[i-1][j-1]+que[i][j]) 其中que[i][j]表示第i束花放进第j个花瓶里的情况.有这个转移方程的原因是,每一束花在每一个花瓶里的情况只有两种:放进去了和没放进去.第一种f[i][j-1]就是没放进去,第二种 f[i-1][j-1]+que[i][j]就是放进去了的情况 特殊的,当i>=j时第一种情况不能成立 路径保存死活没想出来,最后

[luoguP1854] 花店橱窗布置(DP)

传送门 f[i][j] 表示前 i 盆花,放到前 j 个花盆中的最优解 pre[i][j] 记录前驱 代码 #include <cstdio> #include <cstring> #include <iostream> #define N 1001 #define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, t; int a[N][N], f[N][N], pre[N][N], s[N]; inline int rea