Surfing

一点小问题，更正一下

if (g_PathIndex[nPathIndex] >= nCities)
{
g_dRatio[nPathIndex] = (double)nGirls / nBoys;
nGirls = nBoys = 0;
return 0;
}

我的解法

#include <stdio.h>

#define N 13

typedef struct _T_AdjNode
{
int nBoys;
int nGirls;
double dRatio;
}TAdjNode;

TAdjNode g_AdjNode[N][N];
int g_Path[2][N];
int g_PathIndex[2] = {0};
double g_dRatio[2] = {0.0};
int nCities, nRoads;

int FindNextNode(int nPathIndex, int nLine)
{
double dRatio = 0;
int nNode = 0;
int i = 0;
int j = 0;
bool bExist = false;

for (j = 0; j < nCities; j++)
{
for (i = 0; i < g_PathIndex[nPathIndex]; i++)
{
if (j == g_Path[nPathIndex][i])
{
bExist = true;
break;
}
}
if (bExist)
{
bExist = false;
continue;
}
if (g_AdjNode[nLine][j].dRatio > dRatio)
{
dRatio = g_AdjNode[nLine][j].dRatio;
nNode = j;
}
}

return nNode;
}

int FindPath(int nPathIndex, int nNode)
{
int nNextNode = 0;
static int nBoys = 0, nGirls = 0;

g_Path[nPathIndex][g_PathIndex[nPathIndex]] = nNode;
g_PathIndex[nPathIndex]++;
if (g_PathIndex[nPathIndex] >= nCities)
{
g_dRatio[nPathIndex] = (double)nGirls / nBoys;
return 0;
}

nNextNode = FindNextNode(nPathIndex, nNode);
nBoys += g_AdjNode[nNode][nNextNode].nBoys;
nGirls += g_AdjNode[nNode][nNextNode].nGirls;
FindPath(nPathIndex, nNextNode);

return 0;
}

int main()
{
int i,j,nGirls,nBoys;
char q = '0';
int nPathIndex = 0;

nCities = nRoads = 0;
i = j = nGirls = nBoys = 0;

printf("Input the number of cities and roads:\n");
scanf("%d %d", &nCities, &nRoads);

if (nCities < 1 || nRoads < 1)
{
return 1;
}

do
{
printf("Input the road index and the number of girls and boys sequentially : "
"from to girls boys\n");
scanf("%d %d %d %d", &i, &j, &nGirls, &nBoys);
getchar();

g_AdjNode[i - 1][j - 1].nBoys = nBoys;
g_AdjNode[i - 1][j - 1].nGirls = nGirls;
g_AdjNode[i - 1][j - 1].dRatio = (double)nGirls / nBoys;
g_AdjNode[j - 1][i - 1].nBoys = nBoys;
g_AdjNode[j - 1][i - 1].nGirls = nGirls;
g_AdjNode[j - 1][i - 1].dRatio = g_AdjNode[i - 1][j - 1].dRatio;

printf("Input finished?(y/n)");
scanf("%c", &q);
getchar();
} while ('y' != q);

//process here
nPathIndex = 0;
for (i = 0; i < nCities; i++)
{
FindPath(nPathIndex, 0);
nPathIndex = g_dRatio[0] <= g_dRatio[1] ? 0 : 1;
g_PathIndex[nPathIndex] = 0;
}

//output the result
nPathIndex = g_dRatio[0] >= g_dRatio[1] ? 0 : 1;
printf("The max ratio is %.3lf\n", g_dRatio[nPathIndex]);\
printf("The best path : \n");
for (i = 0; i < nCities; i++)
{
printf("%d\t", g_Path[nPathIndex][i]);
}
printf("\n");

return 0;
}