poj 3422 Kaka's Matrix Travels (费用流 + 拆点)-白红宇

poj 3422 Kaka's Matrix Travels (费用流 + 拆点)

阅读量：793 次

发布时间：2023-03-03

本文共 2353 字，大约阅读时间需要 7 分钟。

这道题以前做过了，今天有做了一遍，发现比以前顺手多了。

题意

给一个N×N的方阵，从[1,1]到[n,n]走K次，走过每个方格加上上面的数（每一个方格只能向下或向右走），然后这个格上面的数变为0。求可取得的最大的值。

解题思路

拆点 + 费用流；

将每一个点拆分成两个，为了保证只能算一次，流量为1，花费为方格的值。为了保证其他路径可以从这个点走过，再建一条流量为inf，费用为0的边。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #define Min(a,b) a
             
              b?a:b#define CL(a,num) memset(a,num,sizeof(a))#define eps 1e-12#define inf 10001000#define mx 1<60#define ll __int64#include 
              
               #include 
               
                #define read() freopen("data.txt","r",stdin)const double pi = acos(-1.0);const int maxn = 100000;using namespace std;int n, m, k, s, ss, t, N;int mat[60][60], dis[6000], head[6000], cnt, pre[6000];bool vis[6000];struct node { int v; int cost; int flow; int next;} p[maxn];struct qnode { int u; int len;} qnode;void add(int u, int v, int f, int c) { p[cnt].v = v; p[cnt].cost = c; p[cnt].flow = f; p[cnt].next = head[u]; head[u] = cnt++; p[cnt].v = u; p[cnt].cost = -c; p[cnt].flow = 0; p[cnt].next = head[v]; head[v] = cnt++;}void build() { CL(head, -1); cnt = 0; N = n * n; s = n * n * 2 + 1; t = n * n * 2 + 2; add(s, 0, k, 0); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { a = i * n + j; add(a, a + N, 1, mat[i][j]); add(a + N, inf, 0); if (i + 1 < n) { b = (i + 1) * n + j; add(a + N, b, inf, 0); } if (j + 1 < n) { b = i * n + (j + 1); add(a + N, b, inf, 0); } if (i == n - 1 && j == n - 1) { add(a + N, t, inf, 0); } } }}bool spfa(int s) { int i; for (i = 0; i < t; i++) { dis[i] = -inf; } dis[s] = 0; CL(vis, false); while (!que.empty()) que.pop(); vis[s] = true; que.push(qnode(s, 0)); while (!que.empty()) { a = que.front(); que.pop(); u = a.u; len = a.len; vis[u] = false; for (i = head[u]; i != -1; i = p[i].next) { v = p[i].v; cost = p[i].cost; flow = p[i].flow; if (flow > 0 && dis[v] < dis[u] + cost) { dis[v] = dis[u] + cost; pre[v] = i; if (!vis[v]) { vis[v] = true; que.push(qnode(v, dis[v])); } } } } return dis[t] > 0;}void solve() { int i, j, res = -inf; int tp = t; while (tp != s) { mi = min(p[pre[tp]].flow); tp = p[pre[tp]^1].v; } while (tp != s) { ans += p[pre[tp]].cost; p[pre[tp]].flow--; p[pre[tp]^1].flow += 1; tp = p[pre[tp]^1].v; } printf("%d\n", ans);}int main() { read(); while (scanf("%d%d", n, k) != EOF) { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { scanf("%d", mat[i][j]); } } build(); solve(); }}

转载地址：http://xfxfk.baihongyu.com/

你可能感兴趣的文章