logs 得到 我们 最小费用最大流 str next include ont 价值
给一个N*N的方阵,从[1,1]到[n,n]走K次,走过每个方格加上上面的数,然后这个格上面的数变为0。求可取得的最大的值。
要求最大值,所以把边权全为负跑最小费用即可。因为只有第一次经过该点的时候会得到价值,所以我们将一个点拆为两个,连一条容量为1费用为负权的边和一条容量为k-1费用为0的边。然后和右和下的点连边为容量为k,费用为0的边。跑费用流即可。
- #include < cstdio > #include < queue > #include < algorithm > #include < cstring > #define N 5010#define inf 0x3f3f3f3f using namespace std;
- int n,
- m,
- head[N],
- dis[N],
- cur[N],
- ans,
- cnt = 2,
- s,
- t,
- ANS,
- T,
- a[55][55],
- k;
- queue < int > q;
- bool vis[N];
- struct hhh {
- int to,
- next,
- w,
- cost;
- }
- edge[N * N];
- int read() {
- int ans = 0,
- fu = 1;
- char j = getchar();
- for (; (j < '0' || j > '9') && j != '-'; j = getchar());
- if (j == '-') fu = -1,
- j = getchar();
- for (; j >= '0' && j <= '9'; j = getchar()) ans *= 10,
- ans += j - '0';
- return ans * fu;
- }
- void add(int u, int v, int w, int c) {
- edge[cnt].to = v;
- edge[cnt].w = w;
- edge[cnt].next = head[u];
- edge[cnt].cost = c;
- head[u] = cnt++;
- }
- void addEdge(int u, int v, int w, int c) {
- add(u, v, w, c);
- add(v, u, 0, -c);
- }
- bool bfs() {
- for (int i = s; i <= t; i++) vis[i] = 0,
- cur[i] = head[i],
- dis[i] = inf;
- q.push(s);
- dis[s] = 0;
- vis[s] = 1;
- while (!q.empty()) {
- int r = q.front();
- q.pop();
- vis[r] = 0;
- for (int i = head[r], v; i; i = edge[i].next) {
- v = edge[i].to;
- if (edge[i].w > 0 && dis[r] + edge[i].cost < dis[v]) {
- dis[v] = dis[r] + edge[i].cost;
- if (!vis[v]) {
- vis[v] = 1;
- q.push(v);
- }
- }
- }
- }
- return dis[t] != inf;
- }
- int dfs(int x, int f) {
- if (x == t) return ANS += f * dis[t],
- f;
- int ha = 0,
- now;
- vis[x] = 1;
- for (int & i = cur[x], v; i; i = edge[i].next) {
- v = edge[i].to;
- if (vis[v]) continue;
- if (edge[i].w > 0 && dis[v] == dis[x] + edge[i].cost) {
- now = dfs(v, min(f - ha, edge[i].w));
- if (now) {
- ha += now;
- edge[i].w -= now;
- edge[i ^ 1].w += now;
- }
- }
- if (ha == f) return ha;
- }
- return ha;
- }
- int main() {
- n = read();
- k = read();
- for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) a[i][j] = read();
- s = 0;
- t = 2 * n * n + 1;
- addEdge(s, 1, k, 0);
- for (int i = 1; i <= n; i++) for (int j = 1, p; j <= n; j++) {
- p = n * (i - 1) + j;
- addEdge(p, p + n * n, 1, -a[i][j]);
- addEdge(p, p + n * n, k - 1, 0);
- if (i < n) addEdge(p + n * n, p + n, k, 0);
- if (j < n) addEdge(p + n * n, p + 1, k, 0);
- }
- addEdge(2 * n * n, t, k, 0);
- while (bfs()) ans += dfs(s, inf);
- printf("%d", -ANS);
- return 0;
- }
[poj] 3422 Kaka's Matrix Travels || 最小费用最大流
来源: http://www.bubuko.com/infodetail-2417099.html