首页 > 代码库 > 7/25

7/25

//工厂老师
#include<stdio.h> int minCost = 1000000; int Num, companyNum; int select[100], target[100], companyCost[100], data[31][31]; void getMinCost(int step, int curCost, int count){ int flag = 0; int i, j; if(count==Num) minCost = minCost<curCost?minCost:curCost; if(step==companyNum+1||minCost<=curCost) return; getMinCost(step+1,curCost, count); for(int i = 1; i <= Num; i++) if(select[i]==0){ for(int j = 1;j <= data[step][0]; j++) if(target[i]==data[step][j]){ select[i] = step; count++; break; } } getMinCost(step+1,curCost+companyCost[step], count); for(int i = 1; i <= Num; i++) if(step==select[i]) select[i] = 0; return; } void main(){ int i, j; freopen("input.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &Num); for(i=1;i<=Num;i++) scanf("%d",&target[i]); scanf("%d",&companyNum); for(i=1;i<=companyNum;i++){ scanf("%d %d",&companyCost[i],&data[i][0]); for(j=1;j<=data[i][0];j++) scanf("%d",&data[i][j]); } for(i=1;i<=Num;i++) select[i] = 0; getMinCost(1,0, 0); printf("%d\n",minCost); return; } /// 6 1 5 9 10 11 12 7 15 5 1 3 5 7 9 12 6 2 3 4 6 7 8 7 5 3 4 5 6 7 16 4 8 9 10 11 5 1 2 33 12 1 2 3 4 5 6 7 8 9 10 11 12 9 3 1 12 13

 

7/25