euro efficiency(bellman_ford).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int t, imax;
int coin[20], pay[310];
double avg;

void bellman_ford() {
	int i,j;
	bool flag = true;
	memset(pay,0,sizeof(pay));
	//1 95 96 97 98 99 结果应该是：12.29 25 
	for(i=1;i<=200;i++) pay[i] = 999;
	while(flag) {
		flag = false;
		for(i=0;i<12;i++) {
			for(j=0;j<=200;j++) {
				if(coin[i] + j > 0 && pay[j+coin[i]] > pay[j]+1) {
					flag = true;
					pay[j+coin[i]] = pay[j]+1;
				}
			}
		}
	}
	int sum = 0;
	imax = -1;
	for(i=1;i<=100;i++) sum += pay[i], imax = max(imax, pay[i]);
	avg = 1.0*sum / 100.0;
}

int main() {
	scanf("%d", &t);
	while(t --) {
		int i;
		for(i=0;i<6;i++) scanf("%d", coin+i);
		for(i=0;i<6;i++) coin[6+i] = - coin[i];
		bellman_ford();
		printf("%.2lf %d\n", avg, imax);
	}
}