首页 > 分享 > 花店橱窗布置（带权二分图最大匹配）

花店橱窗布置（带权二分图最大匹配）

花匠小妙招
2024-11-15 23:23

花店橱窗布置

题目描述：
假设以最美观的方式布置花店的橱窗，有F束花，V个花瓶，我们用美学值（一个整数）表示每束花放入每个花瓶所产生的美学效果。为了取得最佳的美学效果，必须使花的摆放取得最大的美学值。
输入描述：
第一行为两个整数F,V(F<=V<=100)
接下来F行每行V个整数，第i行第j个数表示第i束花放入第j个花瓶的美学值。
输出描述 Output Description
一个整数，即最大美学值。
样例输入：
2 2
10 0
5 2
样例输出：
12

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=110; const int inf=0x7fffffff; int n,m,w[maxn][maxn],lx[maxn],ly[maxn],from[maxn],to[maxn]; bool s[maxn],t[maxn]; bool find(int x) { s[x]=1; for(int i=1;i<=m;i++) if(lx[x]+ly[i]==w[x][i]&&!t[i]) { t[i]=1; if(!from[i]||find(from[i])) { from[i]=x; to[x]=i; return 1; } } return 0; } void update() { int d=inf; for(int i=1;i<=n;i++) if(s[i]) for(int j=1;j<=m;j++) if(!t[j]) d=min(d,lx[i]+ly[j]-w[i][j]); for(int i=1;i<=n;i++) if(s[i]) lx[i]-=d; for(int j=1;j<=m;j++) if(t[j]) ly[j]+=d; } void km() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) lx[i]=max(lx[i],w[i][j]); for(int i=1;i<=n;i++) for(;;) { memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); if(find(i)) break; else update(); } } 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(); int ans=0; for(int i=1;i<=n;i++) ans+=w[i][to[i]]; printf("%d",ans); return 0; }