Задача
$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.
Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.
Через какое наименьшее время $T$ минут эта работа будет выполнена?
Входные данные
В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.
Выходные данные
Единственное число — искомое время.
Тесты
| 5 5 4 6 5 4 8 1 6 1 2 3 2 3 5 2 4 2 3 4 6 3 5 4 |
102 |
| 8 10 8 10 8 11 8 0 8 12 8 12 7 8 2 7 6 4 6 2 3 2 1 4 2 3 1 3 1 2 1 5 9 3 5 6 3 4 5 4 5 2 |
690 |
| 11 10 9 5 9 9 9 9 4 9 12 10 10 9 13 3 1 9 1 2 5 2 8 6 2 7 4 1 4 8 4 5 4 4 6 8 1 9 6 9 10 3 10 11 3 |
520 |
| 2 1 3 1 0 6 1 2 10 |
30 |
| 50 50 43 50 44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 41 1 41 42 1 42 43 1 43 44 1 44 45 1 45 46 1 46 44 1 46 48 1 48 49 1 49 50 1 50 1 1 |
8400 |
| 3 3 1 2 3 0 1 1 3 1 2 3 2 1 2 4 |
6 |
Решение 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
#include <iostream> #include <vector> using namespace std; int n,m,b,c; struct boil{ int mass=0; int number=0; vector<boil*> address; vector<int> distance; }; int empty=0; int near_tube=0; vector<int> visit; int Min_way(boil* A, int i, int from){ if(A[i].mass>b){ near_tube=A[i].number; return 0; } int min=0; bool t=0; for(int j=0; j< A[i].distance.size(); j++){ bool t2=true,t1=true; for(int u=0; u<visit.size();u++){ if(visit[u]==A[i].address[j]->number) t2=false; if(visit[u]==A[i].address[min]->number)t1=false; } if(A[i].address[j]->number==empty || A[i].address[j]->number==from)t2=false; if(A[i].address[min]->number==empty || A[i].address[min]->number==from)t1=false; if(A[i].distance[min]>=A[i].distance[j] && t2 || !t1 && t2){ min=j; t=1; } } if(t==0){ if(A[i].distance.size()==1){ if(A[i].address[0]->mass>b){ near_tube=A[i].address[0]->number; return A[i].distance[0]; } else{ return -1; } } else return -1; } else if(A[i].address[min]->mass==b){ visit.push_back(A[i].number); bool t1=true; long long min2=-1; for(int k=0; k<visit.size() && t1; k++){ if(visit[k]==A[i].address[min]->number)t1=false; } if(A[i].address[min]->number==from)t1=false; if(t1) min2=Min_way(A,A[i].address[min]->number,A[i].number); if(min2>=0)min2+=A[i].distance[min]; int n1=near_tube; for(int j=0; j<A[i].distance.size(); j++){ if(j!=min && A[i].address[j]->mass>=b && A[i].address[j]->number!=from){ visit.push_back(A[i].number); long long a=0; bool t3=true; for(int k=0; k<visit.size() && t3; k++){ if(visit[k]==A[i].address[j]->number)t3=false; } if(A[i].address[j]->number==A[empty].number)t3=false; if(t1 && t3){ a=Min_way(A,A[i].address[j]->number,A[i].number); } else return-1; if(a>=0)a+=(A[i].distance[j]); if(a>=0 && min2>=a && A[near_tube].mass>b ||min2<0){ min2=a; n1=near_tube; } visit.clear(); } } near_tube=n1; return min2; } else if(A[i].address[min]->mass<b){ return -1; } else{ near_tube= A[i].address[min]->number; return A[i].distance[min]; } } int main() { cin>>n>>m>>b>>c; boil A[n]; for(int i=0; i<n; i++){ int a; cin>>a; A[i].mass=a; A[i].number=i; if(A[empty].mass>a)empty=i; } int d,k,g; while(cin>>d>>k>>g){ A[d-1].address.push_back(&A[k-1]); A[k-1].address.push_back(&A[d-1]); A[k-1].distance.push_back(g); A[d-1].distance.push_back(g); } unsigned long long s=0; while(A[empty].mass<b){ unsigned long long a=Min_way(A,A[empty].number, A[empty].number); if(A[near_tube].mass-b+A[empty].mass<b){ A[empty].mass+=A[near_tube].mass-b; s+=a*(A[near_tube].mass-b); A[near_tube].mass=b; } else{ int tmp=b-A[empty].mass; A[near_tube].mass-=tmp; A[empty].mass=b; s+=a*tmp; } } cout<<s*c; return 0; } |
Решение 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> #include <queue> #include <vector> using namespace std; struct boil{ int mass = 0; int len = 0; char n/*new*/='y';//yes char visit = 'n';//no vector <int> link; vector <int> dis; }; int main() { int N,M,B,C; cin >> N >> M >> B >> C; boil A[N]; int need; for(int i = 0; i < N ; i++){ cin >> A[i].mass; if(A[i].mass < B)need = i; } int a, b, s; while(cin >> a >> b >> s){ a--; b--; A[a].link.push_back(b); A[a].dis.push_back(s); A[b].link.push_back(a); A[b].dis.push_back(s); } queue <int> A_tmp; A_tmp.push(need); A[need].n = 'n'; int ans = 0; while(!(A_tmp.empty())){ int u = A_tmp.front(); A_tmp.pop(); A[u].visit = 'y';//yes for(int i = 0;i < A[u].link.size(); i++){ if(A[A[u].link[i]].visit == 'n') A_tmp.push(A[u].link[i]); if(A[A[u].link[i]].len>A[u].len+A[u].dis[i] || A[A[u].link[i]].n == 'y'){ A[A[u].link[i]].len = A[u].len + A[u].dis[i]; A[A[u].link[i]].n = 'n'; } } } while(A[need].mass < B){ int m = 0; for(int i = 0; i < N; i++){ if((A[i].len < A[m].len || A[m].mass <= B) && i != need && A[i].mass > B) m = i; } if(A[need].mass + (A[m].mass - B) <= B){ ans += A[m].len * (A[m].mass - B); A[need].mass += A[m].mass - B; A[m].mass = B; } else{ ans += A[m].len * (B - A[need].mass); int b = B - A[need].mass; A[need].mass = B; A[m].mass -= B - A[need].mass; } } cout << ans * C; return 0; } |
Объяснение 1
Вряд ли было бы понятно, если бы я начал сейчас здесь подробно объяснять код. Поэтому, пояснение именно кода я оставлю по этой ссылке, а тут попробую объяснить идею.
Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.
Объяснение 2
И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.
Комментаторам:
Возможно, станет чуть-чуть понятнее, что откуда взялось, если взглянуть на этот код. Это мой черновик к данной задаче. Он не проходит все тесты, но зато там есть некоторые пометки, которые я, вполне возможно, сам же и пропустил. Так что, если хотите подсказать что-то— вряд ли, конечно, но может быть это поможет.
Если код не проходит все тесты, то работа будет оценена максимум в один бал.
Спасибо за напоминание. Но, как я уже писал выше, то— черновик и оставлен он здесь сугубо из-за комментариев в нём. Код-решение можно случайным образом обнаружить, если прокрутить страницу чуточку выше, до ссылки «ideone»
Уточнение: Тест, который не проходился с циклом «for» — пятый. Есть определённая доля вероятности, что там есть некоторая ошибка. В частности, дано не M строк, а M+1
Кирилл, обрати внимание на раздел в котором ты объясняешь идею решения задачи, ты дважды подряд используется слово «достаточно».
Да, спасибо
Для данной задачи достаточно алгоритма Дейкстры. Его сложность $O\left(m\cdot\log n\right)$, а у Вас, как я могу догадываться, что-то близкое к экспоненте. Но главное, что сложность его объяснения и понятность кода являются безусловно выигрышными в сравнении с Вашим текущим решением.
Да, тогда задачу можно будет зачесть на графы.
Только лучше не убирать этот код и пояснение.
Как на фотографиях «до и после»?
Будет виден прогресс алгоритмической мысли 🙂
Алгоритмическая мысль, видимо, несколько продвинулась 🙂 По поводу 88 строчек— судя по всему, так из word копируются таблицы. Постараюсь учитывать в дальнейшем
Да, спасибо, учёл, попробовал сделать. Только не уверен, что за логарифмическую сложность вышло, хотя, если не ошибаюсь, похоже на то