3213000_ac_0ms_388k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int n, m;
double c[101][101], R[101][101];

void init()
{
	int i, j;

	memset(c,0,sizeof(c));
	c[0][0] = c[0][n] = c[n-1][n-1] = 1;
	for(i = 1; i < n-1; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(i!=j&&R[i][j]!=0)
			{
				c[i][j] = -1.0/(R[i][j]);
				c[i][i] += -c[i][j];
			}
		}
	}
}

void gauss()
{
	int i, j, k;
	double tmp, current;
	
	for(i = 0; i < n; ++i)
	{	
		tmp = c[i][i];
		for(j = i; j <= n; ++j)
		{
			c[i][j] /= tmp;
		}
		for(j = i+1; j <n ; ++j)
		{
			tmp = c[j][i];
			for(k = i; k <= n; ++k)
			{
				c[j][k]-=tmp*c[i][k];
			}
		}
	}
	for(i = n-1; i >= 0; --i)
	{
		for(j = i-1; j >= 0; --j)
		{
			tmp = c[j][i]/c[i][i];
			c[j][i]=0;
			c[j][n]-=tmp*c[i][n];
		}
	}
	current = 0;
	for(i = 1; i < n; i++)
	{
		if(R[0][i]!=0)
		{
			current += (1-c[i][n])/(R[0][i]);
		}
	}
	printf("%.2lf\n",1.0/current);
}

int main()
{
	int i;
	int a, b;
	double r;

	scanf("%d%d",&n,&m);
	memset(R,0,sizeof(R));
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%lf",&a,&b,&r);
		a--;b--;
		if(R[a][b]==0)
		{
			R[a][b] = R[b][a] = r;
		}
		else
		{
			R[a][b] = R[a][b]*r/(R[a][b]+r);
			R[b][a] = R[a][b];
		}
	}
	init();
	gauss();
	return 0;
}