2014鞍山ネットワーク予選1010(縮点+ガウス消元)hdu 5006
3272 ワード
Resistance
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 280 Accepted Submission(s): 82
Problem Description
Recently DRD got a number of wires. Some of the wires have the resistance 1 ohm while the others have the resistance 0 ohm. Each wire has probability 50% to be 0 ohm or 1 ohm.
Now ATM gets a circuit board. There are N points in the circuit board. DRD wants to connect these points using his wires. He chooses a wire randomly and chooses two points in the board randomly. Then he will connect the two points using the wire he chooses. DRD will use M wires. Note that it's possible that there exist two points which are not connected by wires.
ATM is interested in the equivalent resistance between the point S and point T. Since they lack of instruments, they want you to calculate the answer.
Input
The first line contains an integer T, denoting the number of the test cases.
For each test case: The first line contains 4 integers: N, M, S, and T. For each of the next M lines, it contains 3 integers: u, v, and c, representing that DRD uses a wire, whose resistance is c, to connect the point u and v. It's guaranteed that 1 <= N <= 10000 and M = 4*N. 1 <= u, v <= N. c is randomly chosen from {0, 1} and u and v are randomly chosen from {1, 2, ..., N}. Note that u can equal v.
Output
For each test case, output a real number. There must be exactly 6 digits after the decimal point. If S and T are not connected by wires, output "inf"(without quotes) instead.
Sample Input
Sample Output
标题:RT
考え方:これは実は高校の物理の問題で、私を酔わせてはいけません
まず、エッジの抵抗が0であることは意味がないので、隣接するすべてのエッジが0である点をマージすることができます.
データはランダムなので、すべてのマージポイントの後に残ったポイントは多くありません.
ここでは各点の電位をUiとし,キルホフ電流の法則によれば,1点に流入する電流は流出する電流に等しい
では、任意の点iに対してΣ(UI-Uj)/Rij=0があり、点jがiの隣接点である
各点に対してこの式があるので,今はn個の未知数,n個の方程式であり,ちょうどGauss消元で解くことができる.
解を容易に得るために、回路全体に初期電流1アンペアを与え、S点から進み、T点から出ることができる.
では初期化時Σ(Us-Uj)/Rsj=1,Σ(Ut-Uj)/Rtj=-1,その他のこの値は0とする
電流は電位差だけに関係するので,このように初期化した後には必ず無限の解があり,Gauss消元は解けない.
そしてそれを防ぐために,いずれかのノード(どのノードでもよい)の電位が定数であると仮定すると,すべての点の電位が固定され,必ず解が得られる.
初期化された電流が1 Aであるため、答えは直接(Us-Ut)/1であり、総抵抗=総電位差/総電流である
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 280 Accepted Submission(s): 82
Problem Description
Recently DRD got a number of wires. Some of the wires have the resistance 1 ohm while the others have the resistance 0 ohm. Each wire has probability 50% to be 0 ohm or 1 ohm.
Now ATM gets a circuit board. There are N points in the circuit board. DRD wants to connect these points using his wires. He chooses a wire randomly and chooses two points in the board randomly. Then he will connect the two points using the wire he chooses. DRD will use M wires. Note that it's possible that there exist two points which are not connected by wires.
ATM is interested in the equivalent resistance between the point S and point T. Since they lack of instruments, they want you to calculate the answer.
Input
The first line contains an integer T, denoting the number of the test cases.
For each test case: The first line contains 4 integers: N, M, S, and T. For each of the next M lines, it contains 3 integers: u, v, and c, representing that DRD uses a wire, whose resistance is c, to connect the point u and v. It's guaranteed that 1 <= N <= 10000 and M = 4*N. 1 <= u, v <= N. c is randomly chosen from {0, 1} and u and v are randomly chosen from {1, 2, ..., N}. Note that u can equal v.
Output
For each test case, output a real number. There must be exactly 6 digits after the decimal point. If S and T are not connected by wires, output "inf"(without quotes) instead.
Sample Input
2
10 40 6 1
9 4 1
7 3 1
10 1 0
5 2 0
6 7 1
7 3 1
3 5 1
3 6 1
8 10 0
8 3 0
7 3 1
3 9 1
2 8 1
10 5 0
10 2 1
10 9 1
9 1 0
7 5 1
10 2 0
8 1 0
2 8 0
10 2 0
1 5 0
5 4 0
7 4 1
8 5 1
4 3 1
6 1 1
5 10 0
3 9 1
5 1 0
9 2 1
3 4 1
5 8 0
3 5 1
3 4 1
2 7 0
4 4 0
1 8 0
10 10 0
10 40 2 1
5 6 1
8 10 1
3 8 1
8 5 0
6 4 1
9 9 1
3 6 1
2 4 1
9 8 0
9 3 0
7 7 1
8 6 1
10 4 1
1 3 0
2 8 1
9 8 0
8 1 1
6 4 0
3 4 0
1 4 0
1 10 0
9 10 0
6 1 1
3 1 1
5 4 0
1 2 1
7 2 1
10 9 0
6 1 0
10 3 1
8 6 1
1 4 0
1 1 0
4 3 0
1 8 0
7 10 1
10 6 0
4 5 0
2 2 0
4 2 1
Sample Output
0.333333
0.222222
标题:RT
考え方:これは実は高校の物理の問題で、私を酔わせてはいけません
まず、エッジの抵抗が0であることは意味がないので、隣接するすべてのエッジが0である点をマージすることができます.
データはランダムなので、すべてのマージポイントの後に残ったポイントは多くありません.
ここでは各点の電位をUiとし,キルホフ電流の法則によれば,1点に流入する電流は流出する電流に等しい
では、任意の点iに対してΣ(UI-Uj)/Rij=0があり、点jがiの隣接点である
各点に対してこの式があるので,今はn個の未知数,n個の方程式であり,ちょうどGauss消元で解くことができる.
解を容易に得るために、回路全体に初期電流1アンペアを与え、S点から進み、T点から出ることができる.
では初期化時Σ(Us-Uj)/Rsj=1,Σ(Ut-Uj)/Rtj=-1,その他のこの値は0とする
電流は電位差だけに関係するので,このように初期化した後には必ず無限の解があり,Gauss消元は解けない.
そしてそれを防ぐために,いずれかのノード(どのノードでもよい)の電位が定数であると仮定すると,すべての点の電位が固定され,必ず解が得られる.
初期化された電流が1 Aであるため、答えは直接(Us-Ut)/1であり、総抵抗=総電位差/総電流である