bzoj 2419 & poj 3532 電阻 題解

【原題】

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 131  Solved: 51

你突破了無數艱難險阻，終于解決了上面那道題，衆神犇瞬間就

震驚了。他們發現居然有人可以把那種非人類做的題目做出來。

他們一緻同意，最後這道題不能再出數學題了。考慮到兩位小盆

友的狀态，他們決定考考你的國中實體水準。 

一個電路闆，有 N 個接點，M 個電阻。電阻兩端都在接點上，

都告訴了你阻值。詢問1 号點與N 号點的等效電阻是多少。 

兩位小盆友很聰明，他們拿出了一個歐姆表，瞬間就虐爆了…不

過你也不甘落後，你肯定不會用這種投機取巧、誤差巨大的方法，

于是你看向了你的電腦。

多組資料，輸入直到檔案結束 

每組資料第一行兩個整數N，M 

接下來 M 行，每行三個非負整數 X，Y，R，表示電阻連接配接的兩

接點和阻值。

每組資料輸出一行，一個實數，四舍五入到小數點後兩位 

2 1

1 2 1

1.00

【分析】首先必須了解一下基爾霍夫定律（感覺很玄乎，但其實很好懂的）。------>

這裡要用到的内容就是：任何一個點（除起點和終點）發出的電流和與接收的電流和相等。即ΣAi=0.

但是這裡有很多未知數，怎麼辦？我不禁想到了高斯消元解方程。設每個點的電勢是ai，那麼對于點i，我們得到的方程就是：

但是起點和終點是不計在内的。因為隻是求等效電阻，我們可以自己設a1（起點）和an（終點）的電勢的值。為了友善，不妨設起點的電勢值為INF，終點的電勢值為0，然後對于剩下的n-2個點分别列n-2的方程，再用高斯消元求解。全部解出之後，再根據基爾霍夫定律——電路中的電流等于終點流入的電流（你也可以算起點流出的電流），求出電路中的電流。最後的等效電阻就是起點和終點的電勢差除以總電流。

【教訓及感想】這道題我一直WA，于是來寫一下做題經過，防止下次再犯同樣的錯誤。

①匆匆寫完程式。因為還夾帶高斯消元，何況沒看題解，心中有點惴惴不安。過了樣例後果然WA了。

②怎麼辦呢？我開始手畫小的資料，然後人工檢驗（畢竟樣例像什麼一樣~~~），結果還是過了。

③我把（你不知道山哥？去百度上打“奶牛異或”，第一個就是。看看相關搜尋，你會有驚喜）在POJ上已過的程式拿來對拍。辛辛苦苦造好資料。

④發現當n<=10的時候都是無壓力的，n>=12開始就會有1.#J這種東西（肯定是除以0了）。于是我把所有可能出現0的地方都特判了——還是照樣挂。

⑤仔細一想，精度被卡了？于是我全開成long double，稍微好了一點。

⑤怎麼辦呢？？？通過研究，我發現我的高斯消元的版本不對，會失精度的。（囧）于是迅速改了一下，改成山哥的版本。但是n變大的時候還是挂了。

⑥可是還是挂，上網查題解，原來資料是根據float造的，要全改float。

⑦還是挂。最後我在後面加了個eps，終于過了。艱辛。

【代碼】