题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5006
题意：有n个节点，有m=4*n条边， 每条边有电阻（只能为0或1， 且它们出现的几率是等概率的）。 询问s, t之间的电阻。（1 ≤ n ≤ 10000. 1 ≤ s, t ≤ n） 保证数据均为随机生成。
思路：由于数据的特性， 可以先用并查集缩点， 将由电阻为0的边连起来的节点缩在一起， 最后剩下的点不会很多， 可以列方程用高斯消元来求解。
考虑对每个点根据连边关系（现在只考虑那些缩点后的点和电阻为1的边）来列方程， 根据电流平衡， 每个点的流入电流=流出电流， 有 ∑(a,b)(Ua−Ub)Rab=0 ， 其中(a, b)为a连出去的边， Rab=1 。 我们让s流入单位1的电流， t流出单位1的电流， 令s的电压为0， 用高斯消元求出t的电压后， s与t之间的电阻即为 Ut 。
关于特殊情况：若s, t被缩到同一点则答案为0， 如果s,t不联通则为inf。
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #define db double #define eps 1e-8 const int N = (int)1e4 + 10; const int M = N * 4; using namespace std; int T, n, m, s, t; int fa[N], tot, id[N], edge[M][2]; int cnt, lst[N], nxt[M], to[M]; int find(int x){ if (x != fa[x]) return fa[x] = find(fa[x]); return x; } void add(int u, int v){ nxt[++ cnt] = lst[u]; lst[u] = cnt; to[cnt] = v; nxt[++ cnt] = lst[v]; lst[v] = cnt; to[cnt] = u; } int num; db G[2000][2000]; bool findd, vis[N]; void dfs(int u){ num ++; vis[u] = 1; if (u == id[find(s)]) G[num][tot + 1] = -1; if (u == id[find(t)]) G[num][tot + 1] = 1, findd = 1; for (int j = lst[u]; j; j = nxt[j]){ int v = to[j]; G[num][u] ++, G[num][v] --; } for (int j = lst[u]; j; j = nxt[j]){ int v = to[j]; if (vis[v]) continue; dfs(v); } } db Gauss(){ int now = 1; for (int i = 1; i <= tot; i ++){ int p = now; db tmp; for (; fabs(G[p][i]) < eps && p <= num; p ++); if (p > num) continue; for (int j = 1; j <= tot + 1; j ++) swap(G[p][j], G[now][j]); tmp = G[now][i]; for (int j = 1; j <= tot + 1; j ++) G[now][j] /= tmp; for (int j = 1; j <= num; j ++) if (j != now){ tmp = G[j][i]; for (int k = 1; k <= tot + 1; k ++) G[j][k] -= tmp * G[now][k]; } now ++; } for (int j = 1; j <= num; j ++) if (fabs(G[j][id[find(t)]] - 1) < eps) return G[j][tot + 1]; return -1; } int main(){ for (scanf("%d", &T); T --; ){ scanf("%d %d %d %d", &n, &m, &s, &t); for (int i = 1; i <= n; i ++) fa[i] = i, id[i] = 0; m = 0; for (int i = 1, u, v, c; i <= 4 * n; i ++){ scanf("%d %d %d", &u, &v, &c); if (c) m ++, edge[m][0] = u, edge[m][1] = v; else if (find(u) != find(v)){ fa[find(u)] = find(v); } } for (int i = 1; i <= n; i ++) if (find(i) == i) id[i] = ++ tot; if (find(s) == find(t)) {printf("%.6lf\n", 0.0); continue;} cnt = 0; memset(lst, 0, sizeof(lst)); for (int i = 1, u, v; i <= m; i ++){ u = edge[i][0], v = edge[i][1]; if (find(u) == find(v)) continue; u = find(u), v = find(v); add(id[u], id[v]); } num = 0; memset(G, 0, sizeof(G)); memset(vis, 0, sizeof(vis)); findd = 0; dfs(id[find(s)]); num ++; G[num][id[find(s)]] = 1, G[num][tot + 1] = 0; if (!findd) puts("inf"); else { printf("%.6lf\n", Gauss()); } } return 0; }