分析：其实就是求矩形中某一个点到其他点的距离加权最小
方法一：
对每一个点求其到其他点的加权距离，然后比较最小。由于有M*N个点，对每一个点求加权距离是O（M*N）的，所以整体时间复杂度是O（M*M*N*N）的。
方法二：
首先做预处理，计算每一行有多少个点，每一列有多少个点，然后计算把其他行的点挪到我这一行需要的加权距离，把其他列的点挪到我这一列的加权距离，
然后对每一个点，计算挪到其所在行的代价+所在列的代价和，求出最小。时间复杂度O（M*N）。
code见下面，calcMIN是方法一，calcDiego是方法二。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define MAX_SIZE 500 int arr[MAX_SIZE][MAX_SIZE];
int sumOfRow[MAX_SIZE];
int sumOfCol[MAX_SIZE];
int costOfRow[MAX_SIZE];
int costOfCol[MAX_SIZE]; int rtnRow;
int rtnCol; int calcCost(int row, int col, int x, int y)
{
int cost = ;
for(int i = ; i < row; i++)
{
for(int j = ; j < col; j++)
{
if(arr[i][j] != )
{
cost += (abs(x-i) + abs(y-j)) * arr[i][j];
}
}
}
return cost;
} void calcMin(int row, int col)
{
long long minCost = LLONG_MAX;
long long tmpCost = ;
for(int i = ; i < row; i++)
{
for(int j = ; j < col; j++)
{
tmpCost = calcCost(row, col, i, j);
if(tmpCost < minCost)
{
minCost = tmpCost;
rtnRow = i;
rtnCol = j;
}
}
}
} void calcDiego(int row, int col)
{
for(int i = ; i < row; i ++)
{
sumOfRow[i] = ;
costOfRow[MAX_SIZE] = ;
} for(int j = ; j < col; j++)
{
sumOfCol[j] = ;
costOfCol[MAX_SIZE] = ;
} for(int i = ; i < row; i ++)
{
for(int j = ; j < col; j++)
{
sumOfRow[i] += arr[i][j];
sumOfCol[j] += arr[i][j];
}
} for(int i = ; i < row; i ++)//cost for moving row j to row i
{
for(int j = ; j < row; j ++)
{
if(i == j || sumOfRow[j] == )
continue;
costOfRow[i] += (abs(j-i)) * sumOfRow[j];
}
} for(int i = ; i < col; i ++)//cost for moving col j to col i
{
for(int j = ; j < col; j ++)
{
if(i == j || sumOfCol[j] == )
continue;
costOfCol[i] += (abs(j-i)) * sumOfCol[j];
}
} int cost = INT_MAX;
for(int i = ; i < row; i ++)
{
for(int j = ; j < col; j ++)
{
if(costOfRow[i] + costOfCol[j] < cost)
{
cost = (costOfRow[i] + costOfCol[j] );
rtnRow = i;
rtnCol = j;
}
}
} } int main()
{
int i, j;
int row, col;
cout << "INT_MAX\t" << INT_MAX << endl;
cout << (500ULL**) << endl;
while (scanf("%d%d", &row, &col) == ) {
for (i = ; i < row; i++)
{
for (j = ; j < col; j++)
{
scanf("%d", &arr[i][j]);
}
}
//printf("calc\n " );
calcMin(row, col);
printf("%d %d\n", rtnRow, rtnCol);
calcDiego(row, col);
printf("%d %d\n", rtnRow, rtnCol); } return ;
}