首页 > ACM题库 > HDU-杭电 > HDU 3976-Electric resistance-数论-[解题报告]HOJ
2015
04-14

HDU 3976-Electric resistance-数论-[解题报告]HOJ

Electric resistance

问题描述 :

Now give you a circuit who has n nodes (marked from 1 to n) , please tell abcdxyzk the equivalent resistance of the circuit between node 1 and node n. You may assume that the circuit is connected. The equivalent resistance of the circuit between 1 and n is that, if you only consider node 1 as positive pole and node n as cathode , all the circuit could be regard as one resistance . (It’s important to analyse complicated circuit ) At most one resistance will between any two nodes.
Easy Fruit Ninja

输入:

In the first line has one integer T indicates the number of test cases. (T <= 100)

Each test first line contain two number n m(1<n<=50,0<m<=2000), n is the number of nodes, m is the number of resistances.Then follow m lines ,each line contains three integers a b c, which means there is one resistance between node a and node b whose resistance is c. (1 <= a,b<= n, 1<=c<=10^4) You may assume that any two nodes are connected!

输出:

In the first line has one integer T indicates the number of test cases. (T <= 100)

Each test first line contain two number n m(1<n<=50,0<m<=2000), n is the number of nodes, m is the number of resistances.Then follow m lines ,each line contains three integers a b c, which means there is one resistance between node a and node b whose resistance is c. (1 <= a,b<= n, 1<=c<=10^4) You may assume that any two nodes are connected!

样例输入:

1 
4 5 
1 2 1 
2 4 4 
1 3 8 
3 4 19 
2 3 12

样例输出:

Case #1: 4.21

高斯消元的模板题

注意用电路中的KCL定理

#include <CSTDIO>
#include <QUEUE>
using namespace std;

/*
hdu 3976
高斯消元
每个节点的流入电流等于流出电流
R = 总电势差/电流
列出方程:
u[i]代表节点i的电势
Σ((u[j]-u[i])/r[i][j]) + I = 0
I[0] = 1
I[n-1] = -1
*/
const int MAXN = 55;
const double _inf = 1e-9;
double a[MAXN][MAXN], x[MAXN]; // 方程左边的矩阵和等式右边的值, x存放最后结果
int equ, val;	// 方程数 未知数个数
inline double mabs(double _X){return _X<0?-_X:_X;}
int gauss()
{
	int i,j,k,col,max_r;
    for(k=0,col=0;k<equ&&col<val;k++,col++)
    {
        max_r=k;
        for(i=k+1;i<equ;i++)
		{
			if(mabs(a[i][col])>mabs(a[max_r][col]))
				max_r=i;
		}
		if(mabs(a[max_r][col])<_inf) return 0;
		if(k!=max_r)
		{
			for(j=col;j<val;j++)
				swap(a[k][j],a[max_r][j]);
			swap(x[k],x[max_r]);
		}
		x[k]/=a[k][col];
		for(j=col+1;j<val;j++)a[k][j]/=a[k][col];
		a[k][col]=1;
		for(i=0;i<equ;i++)
		{
			if(i!=k)
			{
				x[i]-=x[k]*a[i][k];
				for(j=col+1;j<val;j++)a[i][j]-=a[k][j]*a[i][col];
				a[i][col]=0;
			}
		}
    }
    return 1;
}

int n, m;
double data[MAXN][MAXN];
int main()   
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
	int t, cs = 0;
	int i, j;
	double tmp;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n, &m);
		memset(data, 0, sizeof data);
		while (m--)
		{
			scanf("%d%d%lf", &i, &j, &tmp);
			--i, --j;
			data[i][j] = data[j][i] = tmp;
		}
		memset(a, 0, sizeof a);
		memset(x, 0, sizeof x);
		for (i = 0; i< n; ++i)
		{
			for (j = 0; j< n; ++j)
			{
				if (data[i][j])
				{
					a[i][j] += 1.0/data[i][j];
					a[i][i] -= 1.0/data[i][j];
				}
			}
		}
		x[0] = -1;
		x[n-1] = 1;
		equ = val = n;
		gauss();
		printf("Case #%d: %.2lf\n", ++cs, x[0]-x[n-1]);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/solotzg/article/details/9670661


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)