题目链接:uva 10808 - Rational Resistors
题目大意:给出一个博阿含n个节点,m条导线的电阻网络,求节点a和b之间的等效电阻。
解题思路:基尔霍夫定律,任何一点的电流向量为0。就是说有多少电流流入该节点,就有多少电流流出。
对于每次询问的两点间等效电阻,先判断说两点是否联通,不连通的话绝逼是1/0(无穷大)。联通的话,将同一个联通分量上的节点都扣出来,假设电势作为变元,然后根据基尔霍夫定律列出方程,因为对于每个节点的电流向量为0,所以每个节点都有一个方程,所有与该节点直接连接的都会有电流流入,并且最后总和为0,(除了a,b两点,一个为1,一个为-1)。用高斯消元处理,但是这样列出的方程组不能准确求出节点的电势,只能求出各个节点之间电势的关系。所以我们将a点的电势置为0,那么用求出的b点电势减去0就是两点间的电压,又因为电流设为1,所以等效电阻就是电压除以电流。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long type;
struct Fraction {
type member;
type denominator;
Fraction (type member = 0, type denominator = 1);
void operator = (type x) { this->set(x, 1); }
Fraction operator * (const Fraction& u);
Fraction operator / (const Fraction& u);
Fraction operator + (const Fraction& u);
Fraction operator - (const Fraction& u);
Fraction operator *= (const Fraction& u) { return *this = *this * u; }
Fraction operator /= (const Fraction& u) { return *this = *this / u; }
Fraction operator += (const Fraction& u) { return *this = *this + u; }
Fraction operator -= (const Fraction& u) { return *this = *this - u; }
void set(type member, type denominator);
};
inline type gcd (type a, type b) {
return b == 0 ? (a > 0 ? a : -a) : gcd(b, a % b);
}
inline type lcm (type a, type b) {
return a / gcd(a, b) * b;
}
const int maxn = 105;
typedef long long ll;
typedef Fraction Mat[maxn][maxn];
int N, M, f[maxn];
Mat G, A;
bool cmp (Fraction& a, Fraction& b) {
return a.member * b.denominator < b.member * a.denominator;
}
inline int getfar (int x) {
return x == f[x] ? x : f[x] = getfar(f[x]);
}
inline void link (int u, int v) {
int p = getfar(u);
int q = getfar(v);
f[p] = q;
}
void init () {
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++) {
f[i] = i;
for (int j = 0; j < N; j++)
G[i][j] = 0;
}
int u, v;
ll R;
for (int i = 0; i < M; i++) {
scanf("%d%d%lld", &u, &v, &R);
if (u == v)
continue;
link(u, v);
G[u][v] += Fraction(1, R);
G[v][u] += Fraction(1, R);
}
}
Fraction gauss_elimin (int u, int v, int n) {
for (int i = 0; i < n; i++) {
int r;
for (int j = i; j < n; j++)
if (A[j][i].member) {
r = j;
break;
}
if (r != i) {
for (int j = 0; j <= n; j++)
swap(A[i][j], A[r][j]);
}
if (A[i][i].member == 0)
continue;
for (int j = i + 1; j < n; j++) {
Fraction t = A[j][i] / A[i][i];
for (int k = 0; k <= n; k++)
A[j][k] -= A[i][k] * t;
}
}
for (int i = n-1; i >= 0; i--) {
for (int j = i+1; j < n; j++) {
if (A[j][j].member)
A[i][n] -= A[i][j] * A[j][n] / A[j][j];
}
}
return A[u][n] / A[u][u] - A[v][n] / A[v][v];
}
Fraction solve (int u, int v) {
int n = 0, hash[maxn];
int hu, hv;
for (int i = 0; i < N; i++) {
if (i == u)
hu = u;
if (i == v)
hv = v;
if (getfar(i) == getfar(u))
hash[n++] = i;
}
n++;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
A[i][j] = 0;
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
if (i == j)
continue;
int p = hash[i];
int q = hash[j];
A[i][i] += G[p][q];
A[i][j] -= G[p][q];
}
}
A[hu][n] = 1;
A[hv][n] = -1;
A[n-1][0] = 1;
return gauss_elimin (hu, hv, n);
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
init();
int Q, u, v;
scanf("%d", &Q);
printf("Case #%d:\n", kcas);
for (int i = 0; i < Q; i++) {
scanf("%d%d", &u, &v);
printf("Resistance between %d and %d is ", u, v);
if (getfar(u) == getfar(v)) {
Fraction ans = solve(u, v);
printf("%lld/%lld\n", ans.member, ans.denominator);
} else
printf("1/0\n");
}
printf("\n");
}
return 0;
}
Fraction::Fraction (type member, type denominator) {
this->set(member, denominator);
}
Fraction Fraction::operator * (const Fraction& u) {
type tmp_p = gcd(member, u.denominator);
type tmp_q = gcd(u.member, denominator);
return Fraction( (member / tmp_p) * (u.member / tmp_q), (denominator / tmp_q) * (u.denominator / tmp_p) );
}
Fraction Fraction::operator / (const Fraction& u) {
type tmp_p = gcd(member, u.member);
type tmp_q = gcd(denominator, u.denominator);
return Fraction( (member / tmp_p) * (u.denominator / tmp_q), (denominator / tmp_q) * (u.member / tmp_p));
}
Fraction Fraction::operator + (const Fraction& u) {
type tmp_l = lcm (denominator, u.denominator);
return Fraction(tmp_l / denominator * member + tmp_l / u.denominator * u.member, tmp_l);
}
Fraction Fraction::operator - (const Fraction& u) {
type tmp_l = lcm (denominator, u.denominator);
return Fraction(tmp_l / denominator * member - tmp_l / u.denominator * u.member, tmp_l);
}
void Fraction::set (type member, type denominator) {
if (denominator == 0) {
denominator = 1;
member = 0;
}
if (denominator < 0) {
denominator = -denominator;
member = -member;
}
type tmp_d = gcd(member, denominator);
this->member = member / tmp_d;
this->denominator = denominator / tmp_d;
}
分享到:
相关推荐
高校学生成绩管理系统--UML课程设计rational+rose用例图等.zip
学生成绩管理系统----UML课程设计rational+rose用例图,活动图,状态图.rar
IBM--rational rose基础教程 IBM--rational rose基础教程
Rational Suite Enterprise20030610+.part2 正版原盘拷贝,自带lisences V20030610+版本 共四个附件
CC、CQ安装手册-rational CC、CQ安装手册-rational CC、CQ安装手册-rational
NUERBS form of expo-rational B-splines
Rational Suite Enterprise20030610+.part1 正版原盘拷贝 V20030610+版本 共四个附件
Purify - Rational的测试工具使用说明
Rational Suite Enterprise20030610+.part4 正版原盘拷贝,自带lisences V20030610+版本 共四个附件
UML本科生信息管理系统-rational rose 2003
面向对象的可视化建模工具-rational rose
Rational Suite Enterprise20030610+.part3 正版原盘拷贝,自带lisences V20030610+版本 共四个附件
DAEMON rational “C:\Program Files\Rational\common\rational.exe” 将其修改为:SERVER 计算机名 ANY DAEMON rational “自己安装的目录\rational.exe”后,保存 注:若是按默认目录安装,则只需修改计算机名...
data.Rational data.Set data.Stack data.Tuple 以及以下类型类: Bounded Enum Eq Fractional Integral Num Ord Real RealFrac Show Semigroup Monoid 布局 该项目具有以下布局: + bench... JMH benchmarks + core...
stylelint-config-rational-order Stylelint配置,通过按照以下顺序将相关属性声明进行分组来对它们进行排序: 定位 箱型 版式 视觉效果 动画 杂项 . declaration-order { /* Positioning */ position : ...
数值的 Rust的通用Rational (也称为分数)。用法将此添加到您的Cargo.toml : [ dependencies ]num-rational = " 0.4 "特征通过禁用默认的std功能,可以在没有标准库( #![no_std] )的情况下使用此板条箱。 在...
UML建模资料,利用IBM Ration Rose设计
rose2003 中文补丁说明 请先安装Rose2003 。然后下载该程序后选择您安装rose2003的文件位置然后运行。
这是一篇介绍软件架构的英文 作者是:Rational 的Philippe Kruchten
All the key principles of medical decision-making-in one compact, case-based guide "The book provides a comprehensive overview of many core principles in research design and analysis....