深海資源考察探險隊的潛艇將到達深海的海底進行科學考察。潛艇內有多個深海機器人。潛艇到達深海海底后，深海機器人將離開潛艇向預定目標移動。深海機器人在移動中還必須沿途采集海底生物標本。沿途生物標本由最先遇到它的深海機器人完成采集。每條預定路徑上的生物標本的價值是已知的，而且生物標本只能被采集一次。本題限定深海機器人只能從其出發位置沿著向北或向東的方向移動，而且多個深海機器人可以在同一時間占據同一位置。 用一個 P×Q 網格表示深海機器人的可移動位置。西南角的坐標為（0,0），東北角的坐標為 (Q,P)。 
給定每個深海機器人的出發位置和目標位置，以及每條網格邊上生物標本的價值。計算深海機器人的最優移動方案，使深海機器人到達目的地后，采集到的生物標本的總價值最高。
第 1 行為深海機器人的出發位置數 a，和目的地數 b，第 2 行為 P 和 Q 的值。接下來的 P+1 行，每行有 Q 個正整數，表示向東移動路徑上生物標本的價值，行數據依從南到北方向排列。再接下來的 Q+1 行，每行有 P 個正整數，表示向北移動路徑上生物標本的價值，行數據依從西到東方向排列。接下來的 a 行，每行有 3 個正整數 k,x,y，表示有 k 個深海機器人從(x,y)位置坐標出發。再接下來的 b 行，每行有 3 個正整數 r,x,y，表示有 r 個深海機器人可選擇(x,y)位置坐標作為目的地。
輸出采集到的生物標本的最高總價值。
1 1 2 2 1 2 3 4 5 6 7 2 8 10 9 3 2 0 0 2 2 2
42
增加附加源S和附加匯T。 建圖： 1.S向每個出發點連一條容量為該點出發機器人數，費用為0的邊。 2.每個目的點向T連一條容量為該點終止機器人數，費用為0的邊。 3.每點向東、北的相鄰點連一條容量為1，費用為價值的邊。 4.每點向東、北的相鄰點連一條容量為inf，費用為0的邊。 最大費用最大流就是答案。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 1000 + 10, M = 1000000 + 10, inf = 0x3f3f3f3f;struct Edge{ int fr, to, cap, flow, cost;}edg[M];int nxt[M], hd[N], tot;int n, m;int s, t;int q[N], inq[N], p[N], a[N], d[N];int r, c;void insert(int u, int v, int w, int x){ edg[tot].fr = u, edg[tot].to = v, edg[tot].cap = w, edg[tot].flow = 0, edg[tot].cost = x; nxt[tot] = hd[u]; hd[u] = tot; tot++; edg[tot].fr = v, edg[tot].to = u, edg[tot].cap = 0, edg[tot].flow = 0, edg[tot].cost = -x; nxt[tot] = hd[v]; hd[v] = tot; tot++;}bool spfa(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = -inf; d[s] = 0; p[s] = 0; a[s] = inf; int head = 0, tail = 1; q[0] = s; inq[s] = 1; while(head != tail){ int u = q[head++]; if(head == 1001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(d[e.to] < d[u] + e.cost && e.cap > e.flow){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 1001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == -inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}int get(int x, int y){ return x * (m + 1) + y + 1;}void init(){ scanf("%d%d%d%d", &r, &c, &n, &m); memset(hd, -1, sizeof(hd)); int w; s = 0, t = get(n, m) + 1; for(int i = 0; i <= n; i++) for(int j = 0; j < m; j++){ scanf("%d", &w); insert(get(i, j), get(i, j + 1), 1, w); insert(get(i, j), get(i, j + 1), inf, 0); } for(int j = 0; j <= m; j++) for(int i = 0; i < n; i++){ scanf("%d", &w); insert(get(i, j), get(i + 1, j), 1, w); insert(get(i, j), get(i + 1, j), inf, 0); } int x, y; for(int i = 1; i <= r; i++){ scanf("%d%d%d", &w, &x, &y); insert(s, get(x, y), w, 0); } for(int i = 1; i <= c; i++){ scanf("%d%d%d", &w, &x, &y); insert(get(x, y), t, w, 0); }}void work(){ int flow = 0, cost = 0; while(spfa(flow, cost));新聞熱點
疑難解答
