工作效益
http://218.5.5.242:9018/JudgeOnline/problem.php?id=1273
题目描述
给定不同人做不同工作的一个效益矩阵，要求每项工作只能分配一人完成，一人也最多分配一个工作，试编程求解完成工作最大效益。
输入
第一行两个数分别为人数n和工作数m，n≥m且1≤n,m≤20。
以下n行，每行m个数字，其中第i行第j列表示第i个人做第j项工作的效益。
输出
输出一个整数，表示最大的工作效益。
样例输入
5 5 13 11 10 4 7 13 10 10 8 5 5 9 7 7 4 15 12 10 11 5 10 11 8 8 4
样例输出
50
题解
仅仅剪枝过不了。。要加一些贪心的搜索策略QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int n,m,ans,Now; int a[25][25],sum[25],mx[25]; int id[25][25]; bool mark[25]; bool cmp(int x,int y) { return a[x][Now]>a[y][Now]; } void dfs(int x,int tot) { if(tot+sum[x]<=ans) return; if(x==m+1) { ans=max(ans,tot); return; } for(int i=1;i<=n;i++) { int t=id[x][i]; if(!mark[t]) { mark[t]=1; dfs(x+1,tot+a[t][x]); mark[t]=0; } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mx[j]=max(mx[j],a[i][j]); for(int i=1;i<=m;i++) { Now=i; for(int j=1;j<=n;j++) id[i][j]=j; sort(id[i]+1,id[i]+n+1,cmp); } for(int i=m;i;i--) sum[i]=sum[i+1]+mx[i]; dfs(1,0); printf("%d\n",ans); return 0; } |
Subscribe