hdu 4862 Jump
方法一：
用最小K路径覆盖的模板，将每个点拆分为两点表示入和出（标号i，i+N）。源点S向每个i点连边（val = 1, cost = 0），i+N向汇点T连边（val = 1, cost = 0）。若i与j满足题中的关系，则 i 向 j+N连边（val = 1,cost = 点之间移动时能量变化的值）。但每个点入度出度不一定相等（即其可能为起始点），所以加入一个点使其与所有j+N连边（val
= 1, cost = 0），且S与其相连（val = k, cost = 0）。若不满流，则说明k值过小以至于有些点没有被访问。#include<stdio.h> #include<queue> using namespace std; const int MAXN = 500, inf = 0x3f3f3f3f; struct _edge { int v, next, val, cost; _edge(){} }e[MAXN*MAXN]; int head[MAXN], cnt, fa[MAXN], dis[MAXN], vis[MAXN], pos[MAXN]; int n, m; inline void add(int u, int v, int val, int c) { e[cnt].v = v; e[cnt].val = val, e[cnt].cost = c; e[cnt].next = head[u]; head[u] = cnt++; e[cnt].v = u; e[cnt].val = 0; e[cnt].cost = -c; e[cnt].next = head[v]; head[v] = cnt++; } bool spfa(int s, int t) { for(int i = 0; i<= t; ++i) fa[i]=-1,dis[i]=inf,vis[i]=0; int bg = 0, ed = 0; queue<int> q; q.push(s); dis[s] = 0; vis[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i=e[i].next) { int v = e[i].v; if (e[i].val > 0 && dis[v] > dis[u]+e[i].cost) { dis[v] = dis[u]+e[i].cost; fa[v] = u; pos[v] = i; if (!vis[v]) { vis[v] = 1; q.push(v); } } } } return fa[t] != -1; } void minCost_maxFlow(int s, int t, int all) { int cost = 0, f = 0; while (spfa(s,t)) { for (int i=t; i!=s; i=fa[i]) e[pos[i]].val--, e[pos[i]^1].val++; cost += dis[t]; ++f; } if (f != all) printf("-1\n"); else printf("%d\n", -cost); } int mp[15][15]; char str[20]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int k, T, cs = 1, N, s, t, i, j, c, p; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &m, &k); printf("Case %d : ", cs++); N = n*m; s = N*2+1; t = N*2+2; cnt = 0; memset(head, -1, sizeof head); for (i = 0; i< n; ++i) { scanf("%s", str); for (int j = 0; j< m; ++j) mp[i][j] = str[j]-'0'; } for (i = 0, p=0; i< n; ++i) { for (j = 0; j< m; ++j) { p = i*m+j; add(s, p, 1, 0); add(2*N, p+N, 1, 0); add(p+N, t, 1, 0); for (c=1; i+c < n; ++c) { if (mp[i+c][j] == mp[i][j]) add(p, p+m*c+N, 1, -mp[i][j]+c-1); else add(p, p+c*m+N, 1, c-1); } for (c=1; j+c < m; ++c) { if (mp[i][j+c] == mp[i][j]) add(p, p+c+N, 1, -mp[i][j]+c-1); else add(p, p+c+N, 1, c-1); } } } add(s, N*2, k, 0); minCost_maxFlow(s, t, N); } return 0; }方法二：
借用于hdu 4411 相同的思想，因为每个点必须被且仅被访问一次，所以将点拆分为两部分i和i+N，i与i+N连边（val=1，cost = inf或 -inf，取极大或极小按个人习惯），若i和j符合题中关系，则i+N与j连边（val = inf, cost=点之间移动时能量变化的值）。添加辅助点SS，TT。SS向每个 i 连边（val = inf， cost = 0），每个i+N向TT连边（val = inf， cost = 0）。SS向TT连边（val =
k， cost = 0）以防止k值过大。最后源点S向SS连边（val=k，cost=0），TT向T连边（val=k，cost=0）。若k < min(n, m)则说明必定无法照顾到每个点，否则必定可以满流。算出最终的费用后 -inf | +inf * n*m#include<cstdio> #include<iostream> #include<queue> using namespace std; const int MAXN = 250, inf = 0x3f3f3f; struct _edge { int v, next, val, cost; _edge(){} _edge(int a, int b, int c, int d):v(a),next(b),val(c),cost(d){} }e[MAXN*MAXN]; int head[MAXN], cnt, fa[MAXN], dis[MAXN], vis[MAXN], pos[MAXN]; int n, m; inline void add(int u, int v, int val, int c) { e[cnt] = _edge(v, head[u], val, c); head[u] = cnt++; e[cnt] = _edge(u, head[v], 0, -c); head[v] = cnt++; } bool spfa(int s, int t) { for(int i = 0; i<= t; ++i) fa[i]=-1,dis[i]=-inf,vis[i]=0; int bg = 0, ed = 0; queue<int> q; q.push(s); dis[s] = 0; vis[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i=e[i].next) { int v = e[i].v; if (e[i].val > 0 && dis[v] < dis[u]+e[i].cost) { dis[v] = dis[u]+e[i].cost; fa[v] = u; pos[v] = i; if (!vis[v]) { vis[v] = 1; q.push(v); } } } } return fa[t] != -1; } void minCost_maxFlow(int s, int t) { int cost = 0; while (spfa(s,t)) { int mn = inf; for (int i = t; i!= s; i = fa[i]) { if (mn > e[pos[i]].val) mn = e[pos[i]].val; } for (int i = t; i!=s; i=fa[i]) { e[pos[i]].val -= mn; e[pos[i]^1].val += mn; } cost += dis[t]*mn; } printf("%d\n", cost-n*m*inf); } char mp[15][15]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int k, T, cs = 1; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &m, &k); printf("Case %d : ", cs++); int N = n*m; int ss = N*2, tt = N*2+1; int s = tt+1, t = tt+2; cnt = 0; memset(head, -1, sizeof head); for (int i = 0; i< n; ++i) scanf("%s", mp[i]); if (k < min(n, m)) { printf("-1\n"); continue; } for (int i = 0; i< n; ++i) { for (int j = 0; j< m; ++j) { int p = i*m+j; add(ss, p, inf, 0); add(p+N, tt, inf, 0); add(p, p+N, 1, inf); for (int c=1; i+c < n; ++c) if (mp[i+c][j] == mp[i][j]) add(p+N, p+m*c, inf, mp[i][j]-'0'-c+1); else add(p+N, p+c*m, inf, -c+1); for (int c=1; j+c < m; ++c) if (mp[i][j+c] == mp[i][j]) add(p+N, p+c, inf, mp[i][j]-'0'-c+1); else add(p+N, p+c, inf, -c+1); } } add(ss, tt, k, 0); add(s, ss, k, 0); add(tt, t, k, 0); minCost_maxFlow(s, t); } }