生活随笔
收集整理的這篇文章主要介紹了
[codevs 1917] 深海机器人问题
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
[codevs 1917] 深海機(jī)器人問(wèn)題
題解：
看題建圖。
“k個(gè)深海機(jī)器人從(x,y)位置坐標(biāo)出發(fā)”、“r個(gè)深海機(jī)器人可選擇(x,y)位置坐標(biāo)作為目的地”，嗯~暗示已經(jīng)很清楚了。
一開(kāi)始沒(méi)理解題目中關(guān)于地圖大小的敘述，還要記得建立多重邊（有點(diǎn)方格取數(shù)2的味道）。
代碼：
總時(shí)間耗費(fèi): 5ms?
總內(nèi)存耗費(fèi): 364B
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;const int maxn = 500 + 10;
const int INF = 1e9 + 7;struct Edge {int from, to, cap, flow, cost;
};vector<Edge> edges;
vector<int> G[maxn];void AddEdge(int from, int to, int cap, int cost) {edges.push_back((Edge){from, to, cap, 0, cost});edges.push_back((Edge){to, from, 0, 0, -cost});int m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
}int s, t;
int ID[maxn][maxn];int d[maxn*maxn], p[maxn*maxn], a[maxn*maxn];
bool inq[maxn];bool BellmanFord(int& cost) {for(int i = s; i <= t; i++) d[i] = INF;memset(inq, 0, sizeof(inq));d[s] = 0; inq[s] = 1; a[s] = INF; p[s] = 0;queue<int> Q;Q.push(s);while(!Q.empty()) {int x = Q.front(); Q.pop();inq[x] = 0;for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow && d[e.to] > d[x] + e.cost) {d[e.to] = d[x] + e.cost;p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap-e.flow);if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }}}}if(d[t] == INF) return 0;cost += a[t] * d[t];int x = t;while(x != s) {edges[p[x]].flow += a[t];edges[p[x]^1].flow -= a[t];x = edges[p[x]].from;}return 1;
}void MincostMaxflow() {int cost = 0;while(BellmanFord(cost));cout << -cost << endl;
}int main() {int A, B, m, n;cin >> A >> B >> m >> n; m++; n++; s = 0; t = m*n + 1;for(int x = 1, c = 1; x <= m; x++)for(int y = 1; y <= n; y++, c++)ID[x][y] = c;for(int x = 1; x <= m; x++)for(int y = 1; y < n; y++) {int& from = ID[x][y];int& to = ID[x][y+1];int cost;cin >> cost;AddEdge(from, to, 1, -cost);AddEdge(from, to, INF, 0);}for(int y = 1; y <= n; y++)for(int x = 1; x < m; x++) {int& from = ID[x][y];int& to = ID[x+1][y];int cost;cin >> cost;AddEdge(from, to, 1, -cost);AddEdge(from, to, INF, 0);}for(int i = 1; i <= A; i++) {int k, x, y;cin >> k >> x >> y;AddEdge(s, ID[x+1][y+1], k, 0);}for(int i = 1; i <= B; i++) {int r, x, y;cin >> r >> x >> y;AddEdge(ID[x+1][y+1], t, r, 0);}MincostMaxflow();return 0;
}
總結(jié)
以上是生活随笔為你收集整理的[codevs 1917] 深海机器人问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
