題目鏈接：https://www.luogu.org/problemnew/show/P4012
洛谷 P4012 深海機器人問題
輸入輸出樣例
輸入樣例#1：
1 1 2 2 1 2 3 4 5 6 7 2 8 10 9 3 2 0 0 2 2 2
輸出樣例#1：
42
說明
題解：建圖方法如下：
對于矩陣中的每個點，向東、向北分別與其相鄰點都要連兩條邊（重邊）：
1）容量為1，費用為該邊價值的邊；
2）容量為INF，費用為0的邊（因為多個深海機器人可以在同一時間占據同一位置）。
對于每個起點：從S（源點）到這個點連：容量為該點機器人數，費用為0的邊。
對于每個終點：從這個點到T（匯點）連：容量為該點機器人數，費用為0的邊。
?
代碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 455; 5 const int M = N*4+30; 6 const int INF = 0x3f3f3f3f; 7 struct Edge { int to,next,cap,flow,cost; }edge[M]; 8 int head[N],tol; 9 int pre[N],dis[N]; 10 bool vis[N]; 11 int V; 12 void init(int n) { 13 V = n; 14 tol = 0; 15 memset(head,-1,sizeof(head)); 16 } 17 void addedge(int u,int v,int cap,int cost) { 18 edge[tol].to = v; edge[tol].cap = cap; edge[tol].cost = cost; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; 19 edge[tol].to = u; edge[tol].cap = 0; edge[tol].cost = -cost; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; 20 } 21 bool spfa(int s,int t) { 22 queue<int>q; 23 for(int i = 0;i < V;i++) { 24 dis[i] = INF; 25 vis[i] = false; 26 pre[i] = -1; 27 } 28 dis[s] = 0; 29 vis[s] = true; 30 q.push(s); 31 while(!q.empty()) { 32 int u = q.front(); 33 q.pop(); 34 vis[u] = false; 35 for(int i = head[u]; i != -1;i = edge[i].next) { 36 int v = edge[i].to; 37 if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ) { 38 dis[v] = dis[u] + edge[i].cost; 39 pre[v] = i; 40 if(!vis[v]) { 41 vis[v] = true; 42 q.push(v); 43 } 44 } 45 } 46 } 47 if(pre[t] == -1) return false; 48 else return true; 49 } 50 int minCostMaxflow(int s,int t,int &cost) { 51 int flow = 0; 52 cost = 0; 53 while(spfa(s,t)) { 54 int Min = INF; 55 for(int i = pre[t];i != -1;i = pre[edge[i^1].to]) { 56 if(Min > edge[i].cap - edge[i].flow) 57 Min = edge[i].cap - edge[i].flow; 58 } 59 for(int i = pre[t];i != -1;i = pre[edge[i^1].to]) { 60 edge[i].flow += Min; 61 edge[i^1].flow -= Min; 62 cost += edge[i].cost * Min; 63 } 64 flow += Min; 65 } 66 return flow; 67 } 68 int main() { 69 int a, b, p, q, k, x, y, i, j, ans = 0; 70 scanf("%d%d", &a, &b);//出發和目的地數目 71 scanf("%d%d", &p, &q); 72 init((p+1)*(q+1)+3); 73 74 int s = (p+1)*(q+1)+1, t = (p+1)*(q+1)+2; 75 76 for(i = 0; i <= p; ++i) {//p+1行,向東移動 77 for(j = 0; j < q; ++j) { 78 scanf("%d", &x);//邊上的標本價值 79 addedge(i*(q+1)+j, i*(q+1)+j+1, 1, -x); 80 addedge(i*(q+1)+j, i*(q+1)+j+1, INF, 0); 81 } 82 } 83 for(j = 0; j <= q; ++j) {//q+1列,向北移動 84 for(i = 0; i < p; ++i) { 85 scanf("%d", &x); 86 addedge(i*(q+1)+j, i*(q+1)+j+q+1, 1, -x); 87 addedge(i*(q+1)+j, i*(q+1)+j+q+1, INF, 0); 88 } 89 } 90 for(i = 1; i <= a; ++i) {//起點 91 scanf("%d%d%d", &k, &x, &y); 92 addedge(s, x*(q+1)+y, k, 0); 93 } 94 for(i = 1; i <= b; ++i) {//終點 95 scanf("%d%d%d", &k, &x, &y); 96 addedge(x*(q+1)+y, t, k, 0); 97 } 98 minCostMaxflow(s, t, ans); 99 printf("%d\n", -ans); 100 return 0; 101 }
?
 譯文五、六、七)
