首页 > 代码库 > HDU 4862 Jump (2014-多校1-1002,最小K路径覆盖,最小费用最大流)

HDU 4862 Jump (2014-多校1-1002,最小K路径覆盖,最小费用最大流)

题目:

http://acm.hdu.edu.cn/showproblem.php?pid=4862

 

题意:

给你一个n*m的矩阵,填充着0-9的数字,每次能从一个点出发,到它的右边或者下边的点,花费为|x1-x2|+|y1-y2|-1,如果跳跃的起点和终点的数字相同,则获得这个数字的收益,不能走已经走过的点

有K次重新选择起点的机会

如果可以走遍所有点,则输出最大的价值(收益-花费)

否则,输出-1

 

方法:

最小K路径覆盖,最小费用最大流

建图:

每个点拆为2点:X部和Y部,(a,b)表示流量a,费用b

源点与X部每个点连(1,0)的边

Y部每个点与汇点连(1,0)的边

X部的点如果可以到Y部的点,则连(1,花费-收益)的边

源点与一个新点连(k,0)的边,新点与Y部每个点连(1,0)的边

结果:

如果满流,则输出0-费用

否则,输出-1

 

代码:

  1 // #pragma comment(linker, "/STACK:102400000,102400000")  2 #include <cstdio>  3 #include <iostream>  4 #include <cstring>  5 #include <string>  6 #include <cmath>  7 #include <set>  8 #include <list>  9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 // const int maxn = 210; 23 // const int maxm = 200010; 24 // const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32  33 /** 34 *最小(大)费用最大流:SPFA增广路($O(w*O(SPFA))$) 35 *最大费用:费用取反addEdge(,,,-cost); 36 *输入:图(链式前向星),n(顶点个数,包含源汇),s(源),t(汇) 37 *输出:minCostMaxflow(int s, int t, int &cost)返回流量, cost为费用 38 *打印路径方法:按反向边(i&1)的flow 找,或者按边的flow找 39 */ 40 const int maxn = 210; 41 const int maxm = 200010; 42 const int inf = 0x3f3f3f3f; 43 struct Edge 44 { 45     int u, v; 46     int cap, flow; 47     int cost; 48     int next; 49 } edge[maxm]; 50 int head[maxn], en; //需初始化 51 int n, m; 52 int st, ed; 53 bool vis[maxn]; 54 int pre[maxn], dis[maxn]; 55 void addse(int u, int v, int cap, int flow, int cost) 56 { 57     edge[en].u = u; 58     edge[en].v = v; 59     edge[en].cap = cap; 60     edge[en].flow = flow; 61     edge[en].cost = cost; 62     edge[en].next = head[u]; 63     head[u] = en++; 64 } 65 void adde(int u, int v, int cap, int cost) 66 { 67     addse(u, v, cap, 0, cost); 68     addse(v, u, 0, 0, -cost); //注意加反向0 边 69 } 70 bool spfa(int s, int t) 71 { 72     queue<int>q; 73     for (int i = 0; i < n; i++) 74     { 75         dis[i] = inf; 76         vis[i] = false; 77         pre[i] = -1; 78     } 79     dis[s] = 0; 80     vis[s] = true; 81     q.push(s); 82     while (!q.empty()) 83     { 84         int u = q.front(); 85         q.pop(); 86         vis[u] = false; 87         for (int i = head[u]; i != -1; i = edge[i].next) 88         { 89             int v = edge[i].v; 90             if (edge[i].cap > edge[i].flow && 91                     dis[v] > dis[u] + edge[i].cost ) 92             { 93                 dis[v] = dis[u] + edge[i].cost; 94                 pre[v] = i; 95                 if (!vis[v]) 96                 { 97                     vis[v] = true; 98                     q.push(v); 99                 }100             }101         }102     }103     if (pre[t] == -1)return false;104     else return true;105 }106 int minCostMaxflow(int s, int t, int &cost)//返回流量, cost为费用107 {108     int flow = 0;109     cost = 0;110     while (spfa(s, t))111     {112         int Min = inf;113         for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].v])114         {115             if (Min > edge[i].cap - edge[i].flow)116                 Min = edge[i].cap - edge[i].flow;117         }118         for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].v])119         {120             edge[i].flow += Min;121             edge[i ^ 1].flow -= Min;122             cost += edge[i].cost * Min;123         }124         flow += Min;125     }126     return flow;127 }128 int N, M, K;129 int kase;130 int mtx[maxn][maxn];131 int disxy(int x1, int y1, int x2, int y2)132 {133     return abs(x1 - x2) + abs(y1 - y2) - 1;134 }135 void build()136 {137     n = 3 + N * M * 2;138     st = 0, ed = 1;139     for (int i = 0; i < N; i++)140     {141         for (int j = 0; j < M; j++)142         {143             adde(st, i * M + j + 3, 1, 0);144         }145     }146     adde(st, 2, K, 0);147     for (int i = 0; i < N; i++)148     {149         for (int j = 0; j < M; j++)150         {151             adde(2, i * M + j + N * M + 3, 1, 0);152             adde(i * M + j + N * M + 3, ed, 1, 0);153         }154     }155     for (int i = 0; i < N; i++)156     {157         for (int j = 0; j < M; j++)158         {159             for (int h = i + 1; h < N; h++)160             {161                 if (mtx[i][j] == mtx[h][j])162                 {163                     adde(i * M + j + 3, h * M + j + N * M + 3, 1, h - i - 1 - mtx[i][j]);164                     // cout << i << " " << j << " " << h << " " << j << endl;165                 }166                 else167                 {168                     adde(i * M + j + 3, h * M + j + N * M + 3, 1, h - i - 1);169                 }170             }171             for (int h = j + 1; h < M; h++)172             {173                 if (mtx[i][j] == mtx[i][h])174                 {175                     adde(i * M + j + 3, i * M + h + N * M + 3, 1, h - j - 1 - mtx[i][j]);176                     // cout << i << " " << j << " " << i << " " << h << endl;177                 }178                 else179                 {180                     adde(i * M + j + 3, i * M + h + N * M + 3, 1, h - j - 1);181                 }182             }183         }184     }185 }186 void init()187 {188     memset(head, -1, sizeof(head));189     en = 0;190     kase++;191 }192 void input()193 {194     scanf("%d%d%d", &N, &M, &K);195     for (int i = 0; i < N; i++)196     {197         char str[maxn];198         scanf("%s", str);199         for (int j = 0; j < M; j++)200         {201             mtx[i][j] = str[j] - 0;202         }203     }204 }205 void debug()206 {207     //208 }209 void solve()210 {211     build();212     int cost;213     int flow = minCostMaxflow(st, ed, cost);214     // cout << "flow,cost: " << flow << " " << cost << endl;215     if (flow == N * M)216     {217         printf("Case %d : %d\n", kase, -cost);218     }219     else220     {221         printf("Case %d : %d\n", kase, -1);222     }223 }224 void output()225 {226     //227 }228 int main()229 {230     // int size = 256 << 20; // 256MB231     // char *p = (char *)malloc(size) + size;232     // __asm__("movl %0, %%esp\n" :: "r"(p));233 234     // std::ios_base::sync_with_stdio(false);235 #ifndef ONLINE_JUDGE236     freopen("in.cpp", "r", stdin);237 #endif238 239     kase = 0;240     int T;241     scanf("%d", &T);242     while (T--)243     {244         init();245         input();246         solve();247         output();248     }249     return 0;250 }
HDU 4862