Сопротивление цепи
Цепь из n узлов и m резисторов, к узлам s и t подключена батарейка на V вольт: плюс к s, минус к t. Найдите сопротивление цепи между s и t — во сколько раз напряжение батарейки больше тока, который она отдаёт, — и наибольший ток среди всех резисторов.
По резистору сопротивлением R между узлами с потенциалами φa и φb течёт ток (φa − φb)/R; в каждом узле, кроме s и t, сколько тока втекает, столько и вытекает. Между двумя узлами может быть несколько резисторов, резистор может соединять узел сам с собой, а часть цепи может быть вообще не связана с батарейкой.
Третий тест — улицы вокруг площади Республики в Алматы (OpenStreetMap, ODbL): каждая улица — провод сопротивлением 1 Ом на 100 метров.
Вход
В первой строке n, m, s, t, V (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ s, t ≤ n, s ≠ t, 0 < V ≤ 1000). Дальше m строк a b R: резистор между узлами a и b, 1 ≤ R ≤ 10⁶ Ом.
Выход
Два числа: сопротивление цепи между s и t в омах и наибольший ток в амперах. Если ток от батарейки до t не доходит, выведите -1 0. Числа принимаются с относительной ошибкой до 10⁻⁶ (для чисел меньше единицы — с абсолютной).
Примеры
Пример 1
4 5 1 4 9 1 2 100 1 3 220 2 4 330 3 4 150 2 3 470
191.0441843 0.02737084515
Пример 2
6 5 1 3 12 1 2 100 1 2 100 2 3 50 3 3 10 5 6 1000
100 0.12
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Неизвестные — потенциалы узлов. Сколько уравнений даёт закон Кирхгофа и сколько среди них независимых?
2Подсказка 2
Потенциалы определены с точностью до общей добавки. Что, если объявить один узел «землёй»? И что делать с узлами, до которых ток от батарейки не доходит вовсе — например, со вторым примером?
3Идея
Подадим в s ток 1 А и заберём его из t, а потенциал t примем за ноль. Для остальных узлов закон Кирхгофа даёт систему с матрицей-лапласианом: на диагонали сумма проводимостей 1/R всех резисторов узла, вне диагонали — минус проводимость между соседями (параллельные резисторы складываются). Тогда потенциал s и есть сопротивление цепи: вольты на ампер. Цепь линейна, так что настоящие потенциалы при батарейке на V вольт — эти же, умноженные на V/R.
Но решать систему можно только для узлов, связанных с s. Узел, до которого не дотягивается ни один резистор от батарейки, ничем не привязан к земле, его потенциал может быть любым, и матрица вырождена — метод Гаусса упрётся в нулевой ведущий элемент.
4Разбор
Обходом в глубину от s находим связную часть цепи. Если t в неё не попал, ток не течёт: ответ -1 0. Иначе нумеруем узлы этой части, кроме t, строим матрицу и правую часть с единицей в строке s, решаем методом Гаусса — для такой матрицы выбор ведущего не обязателен, но и не вредит. Сопротивление — потенциал s. Масштабируем потенциалы на V/R и проходим по резисторам связной части, вычисляя |φa − φb|/R.
Проверить себя помогают тесты с известным ответом. Последовательная цепочка: сопротивления складываются, 1 + 2 + … + 199 = 19 900 Ом. Сорок узлов, каждый с каждым через 100 Ом: между любыми двумя ровно 2·100/40 = 5 Ом.
4+Решение
5Сложность
Обход — O(n + m), матрица — O(n²) памяти, метод Гаусса — O(n³): при n = 200 это около трёх миллионов умножений, доли секунды даже на Python.
6Типичные ошибки
- Уравнения для всех узлов подряд. Висящая в воздухе пара узлов делает матрицу вырожденной: деление на ноль во втором тесте.
- Без «земли». Лапласиан связной цепи вырожден сам по себе: его строки в сумме дают ноль. Один узел нужно исключить, приняв его потенциал за ноль.
- Параллельные резисторы. Два резистора между одной парой узлов — это сумма проводимостей, а не последний прочитанный.
- Резистор «сам в себя». Он ничего не меняет: разность потенциалов на нём ноль.