Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <stdio.h>
- #include <deque>
- using namespace std;
- const int INF = (1 << 31) - 1;
- struct Edge {
- int able;
- int cost;
- Edge* brother;
- int vert;
- Edge(int able, int cost, int vert) {
- this -> able = able;
- this -> cost = cost;
- this -> vert = vert;
- }
- };
- //vector<Edge*> graph[700];
- int next[200000];
- int first[700];
- Edge* graph[200000];
- int cnt;
- int n, m;
- int dist[700]; // Âåëè÷èíà êðàò÷àéøåãî ðàññòîÿíèÿ äî i-îé âåðøèíû.
- int from[700]; // Èç êàêîé âåðøèíû ïðèøëè â i-óþ âåðøèíû.
- Edge* fromEdge[700]; // Èç êàêîãî ðåáðà ïðèøëè.
- bool mark[700]; // Ïîìå÷åíà ëè âåðøèíà â àëãîðèòìå.
- int able[700]; //Ñêîëüêî íåôòè ìîæíî ïðîïóñòèòü èç èñòîêà â i-óþ âåðøèíó.
- int type[700];
- deque<int> q;
- long long res;
- int getMinVertex() {
- int res = -1;
- int curDist = INF;
- for (int i = 0; i < n + m + 2; i++) {
- if (dist[i] < curDist && !mark[i]) {
- res = i;
- curDist = dist[i];
- }
- }
- }
- void relaxVertex(int vert) {
- mark[vert] = true;
- for (int i = first[vert]; i != -1; i = next[i]) {
- Edge* e = graph[i];
- if (e -> able > 0 && dist[e -> vert] > dist[vert] + e -> cost) {
- dist[e -> vert] = dist[vert] + e -> cost;
- from[e -> vert] = vert;
- fromEdge[e -> vert] = e;
- able[e -> vert] = min(e -> able, able[vert]);
- }
- }
- }
- void initDijkstra() {
- for (int i = 0; i < n + m + 2; i++) {
- dist[i] = INF;
- mark[i] = false;
- able[i] = INF;
- type[i] = 0;
- }
- dist[0] = 0;
- }
- bool runDijkstra() {
- initDijkstra();
- int vert;
- while ( (vert = getMinVertex()) != -1) {
- relaxVertex(vert);
- }
- return dist[1] != INF;
- }
- void fillPath() {
- int cur = 1;
- long long sumCost = 0;
- while (cur != 0) {
- Edge* e = fromEdge[cur];
- sumCost += e -> cost;
- e -> able -= able[1];
- e -> brother -> able += able[1];
- cur = from[cur];
- }
- res += sumCost * able[1];
- }
- void addEdge(int from, int to, int cost, int able) {
- Edge* e = new Edge(able, cost, to);
- Edge* broth = new Edge(0, -cost, from);
- e -> brother = broth;
- broth -> brother = e;
- //graph[from].push_back(e);
- //graph[to].push_back(broth);
- next[cnt] = first[from];
- first[from] = cnt;
- graph[cnt++] = e;
- next[cnt] = first[to];
- first[to] = cnt;
- graph[cnt++] = broth;
- }
- void readData() {
- scanf("%d%d",&n, &m);
- for (int i = 0; i < n; i++) {
- int able;
- scanf("%d", &able);
- addEdge(0,i + 2, 0, able);
- }
- for (int i = 0; i < m; i++) {
- int able;
- scanf("%d", &able);
- addEdge(2 + n + i, 1, 0, able);
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- int cost;
- scanf("%d", &cost);
- addEdge(i + 2, j + n + 2, cost, INF);
- }
- }
- }
- //
- //void printGraph() {
- // for (int i = 0; i < n + m + 2; i++) {
- // printf("%d\n", i);
- // for (int j = 0; j < graph[i].size(); j++) {
- // Edge* e = graph[i][j];
- // printf("ver: %d, cost: %d, able: %d\n", e -> vert, e -> cost, e -> able);
- // }
- // printf("\n");
- // }
- //}
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- memset(next, -1, sizeof (next));
- memset(first, -1, sizeof (first));
- readData();
- while (runDijkstra()) {
- fillPath();
- }
- cout << res << endl;
- //printGraph();
- fclose(stdout);
- return 0;
- }
Add Comment
Please, Sign In to add comment