编程之美2014

#include <stdio.h>
#include <stdlib.h>

void Gegequshu(int **matrix, int m, int n, int *sum, int t)
{
	int i, j, k;
	int a[100], b[100];
	int min;
	int min_sign;
	for(i = 0; i < m; i++)
		a[i] = 0;
	for(i = 0; i < n; i++)
		b[i] = 0;
	k = 0;
	sum[t] = 0;
	if( m <= n)//行小于列，先把行选满，再处理剩余的列
	{
		for(i = 0; i < m; i++)//行选满
		{
			min = 65535;
			for(j = 0; j < n; j++)
				if(b[j] == 0)
					if(matrix[i][j] < min)
					{
						min = matrix[i][j];
						min_sign = j;
					}
			sum[t] += min;
			b[min_sign] = 1;
		}
		for(i = 0; i < n; i++)//处理剩余的列，选取列中最小值
			if(b[i] == 0)
			{
				min = 65535;
				for(j = 0; j < m; j++)
					if(matrix[j][i] < min)
						min = matrix[j][i];
			
				sum[t] += min;
			}
	}
	else//列小于行，先把列选满，再处理剩余的行
	{
		for(i = 0; i < n; i++)
		{
			min = 65535;
			for(j = 0; j < m; j++)
				if(a[j] ==0)
					if(matrix[j][i] < min)
					{
						min = matrix[j][i];
						min_sign = j;
					}
			sum[t] += min;
			a[min_sign] = 1; 
		}
		for(i = 0; i  < m ; i++)
			if(a[i] == 0)
			{
				min = 65535;
				for(j = 0; j < n; j++)
					if(matrix[i][j] < min)
						min = matrix[i][j];
				sum[t] += min;
			}
	}

}

int main(int argc, char const *argv[])
{
	int t, times;
	scanf("%d", &times);
	int sum[100];
	
	for(t = 0; t < times; t++)
	{
		int i, j;
		int n, m;
		int **matrix;
		scanf("%d%d", &m, &n);
		matrix = (int **)malloc(m * sizeof(int *));
		if(matrix == NULL)
			return 0;
		for(i = 0; i < m; i++)
			matrix[i] = (int *)malloc(n * sizeof(int));
		for(i = 0; i < m; i++)
			for(j = 0; j < n; j++)
				scanf("%d", &matrix[i][j]);
		Gegequshu(matrix, m, n, sum, t);
		for(i = 0; i < m; i++)
			free(matrix[i]);
		free(matrix);
	}
	for(t = 0; t < times; t++)
	{
		printf("Case %d: %d\n", t + 1, sum[t]);
	}

	return 0;
}

编程之美2014,布布扣,bubuko.com

编程之美2014

原文：http://blog.csdn.net/jjjcainiao/article/details/23540561