Volume 1 / 0191

パソコン甲子園2008本選　解答

Problem 0191 : Baby Tree

a（1...m）回目に肥料i（0...n-1）を投入したときの最大成長率を記録していって、最終的にm回目で成長率が最大のものを出力する。

#include <iostream>
#include <iomanip>
#include <vector>
#include <limits.h>

using namespace std;


struct STATE {
	int id;
	double val;
};

vector<STATE> prev, next;
vector< vector<double> > g_table;
int n, m;

void init()
{
	prev.clear(); next.clear();
	prev.resize(n); next.resize(n);

	for( int i=0; i<n; i++ ){
		prev[i].id = i;
		prev[i].val = 1.0;
	}

	return;
}

double calc()
{
	int i, j, k;
	double new_val;
	double result;

	for( i=1; i<m; i++ ){
		for( j=0; j<n; j++ ){
			next[j].val = INT_MIN;
			for( k=0; k<n; k++ ){
				new_val = prev[k].val*g_table[prev[k].id][j];
				if( next[j].val < new_val ){
					next[j].val = new_val;
					next[j].id = j;
				}
			}
		}
		prev = next;
	}

	result = prev[0].val;
	for( i=1; i<n; i++ ){
		if( result < prev[i].val )
			result = prev[i].val;
	}

	return result;
}

int main(void)
{
	int i, j;
	double input;

	while( cin >> n >> m, n != 0 && m != 0 ){
		g_table.clear();
		g_table.resize(n);
		for( i=0; i<n; i++ )
			g_table[i].resize(n);

		for( i=0; i<n; i++ ){
			for( j=0; j<n; j++ ){
				cin >> input;
				g_table[i][j] = input;
			}
		}

		init();
		cout << setprecision(2) << setiosflags(ios::fixed);
		cout << calc() << endl;
	}

	return 0;
}