[codevs 1227] 方格取數 2

題解：

注：這是CODEVS的方格取數2，走k次的版本。

因為每個格子可以走無數次，但走過一次之后數字就變成了0，也就是只有一次可以加上格子里的數字。所以要拆點（X->Xi,Xj），在Xi和Xj之間連一條容量為1，費用為數字的相反數的邊（取走該格數字），再連一條容量為INF，費用為0的邊（第2,3...n次走該格）。再從每個格子的Xj點向左面及下面的格子的Xi點連一條容量為1，費用為0的邊，最后從源點向第一個格子的Xi連一條容量為k（走k次）費用為0，從最后一個點的Xj向匯點連一條同樣的邊。求解最小費用最大流，費用的相反數就是答案。

代碼：

總時間耗費: 149ms?
總內存耗費: 1 kB
#include<cstdio> #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; const int INF = 1e8 + 7; const int maxn = 50 * 50 * 2 + 10;struct Edge{int from, to, cap, flow, cost; };vector<Edge> edges; vector<int> G[maxn]; int n, k, s, t;void encode(int i, int j, int& THIS, int& NEXT, int& DOWN, int& LEFT) {i--; j--;THIS = i * n + j + 1;NEXT = THIS + n*n;DOWN = i < n-1 ? THIS + n : 0;LEFT = j < n-1 ? THIS + 1 : 0; }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 d[maxn], a[maxn], p[maxn]; bool inq[maxn];bool SPFA(int &cost) {for(int i = 0; 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 u = Q.front(); Q.pop();inq[u] = 0;for(int i = 0; i < G[u].size(); i++) {Edge& e = edges[G[u][i]];if(e.cap > e.flow && d[u] + e.cost < d[e.to]) {d[e.to] = d[u] + e.cost;p[e.to] = G[u][i];a[e.to] = min(a[u], e.cap - e.flow);if(!inq[e.to]) {Q.push(e.to);inq[e.to] = 1;}}}}if(d[t] == INF) return 0;cost += d[t] * a[t];int u = t; while(u != s) {edges[p[u]].flow += a[t];edges[p[u]^1].flow -= a[t];u = edges[p[u]].from;}return 1; }int maxflow() {int cost = 0;while(SPFA(cost));return cost; }int main() {cin >> n >> k;s = 0; t = n*n*2 + 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++) {int THIS, NEXT, DOWN, LEFT;encode(i, j, THIS, NEXT, DOWN, LEFT);int w;cin >> w;AddEdge(THIS, NEXT, 1, -w);AddEdge(THIS, NEXT, INF, 0);if(LEFT) AddEdge(NEXT, LEFT, INF, 0);if(DOWN) AddEdge(NEXT, DOWN, INF, 0);}AddEdge(s, 1, k, 0);AddEdge(t-1, t, k, 0);cout << -maxflow() << endl;return 0; }

總結

以上是生活随笔為你收集整理的[codevs 1227] 方格取数2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。