hoj 2715 (费用流 拆点）

http://acm.hit.edu.cn/hoj/problem/view?id=2715

将每个格子 i 拆成两个点 i’, i’’并加边(i’, i’’, 1, -Vi), (i’, i’’, ∞, 0), (s, i’, ∞, 0); 控制只有一次能取到宝物。

对相邻的四个格子 j, Hi > Hj 则加边(i’’, j’, ∞, 0);

若格子 i 在边界上则加边(i’’, t, ∞, 0)。

限制增广次数小于等于 K 求最小费用流即可。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <cmath>

 using namespace std;

 const int maxn = ;

 const int maxm = ;

 const int inf = 0x3f3f3f3f;

 struct MCMF

 {

     struct Edge

     {

         int v, c, w, next;

     }p[maxm << ];

     int e, head[maxn], dis[maxn], pre[maxn], cnt[maxn], sumFlow, n;

     bool vis[maxn];

     void init(int nt)

     {

         e = ; n = nt;

         memset(head, -, sizeof(head[]) * (n + ) );

     }

     void addEdge(int u, int v, int c, int w)

     {

         p[e].v = v; p[e].c = c; p[e].w = w; p[e].next = head[u]; head[u] = e++;

         swap(u, v);

         p[e].v = v; p[e].c = ; p[e].w = -w; p[e].next = head[u]; head[u] = e++;

     }

     bool spfa(int S, int T)

     {

         queue <int> q;

         for (int i = ; i <= n; ++i)

             vis[i] = cnt[i] = , pre[i] = -, dis[i] = inf;

         vis[S] = , dis[S] = ;

         q.push(S);

         while (!q.empty())

         {

             int u = q.front(); q.pop();

             vis[u] = ;

             for (int i = head[u]; i + ; i = p[i].next)

             {

                 int v = p[i].v;

                 if (p[i].c && dis[v] > dis[u] + p[i].w)

                 {

                     dis[v] = dis[u] + p[i].w;

                     pre[v] = i;

                     if (!vis[v])

                     {

                         q.push(v);

                         vis[v] = ;

                         if (++cnt[v] > n) return ;

                     }

                 }

             }

         }

         return dis[T] != inf;

     }

     int mcmf(int S, int T, int kt)

     {

         sumFlow = ;

         int minFlow = , minCost = ;

         while (spfa(S, T) && (kt--))

         {

             minFlow = inf + ;

             for (int i = pre[T]; i + ; i = pre[ p[i ^ ].v ])

                 minFlow = min(minFlow, p[i].c);

             sumFlow += minFlow;

             for (int i = pre[T]; i + ; i = pre[ p[i ^ ].v ])

             {

                 p[i].c -= minFlow;

                 p[i ^ ].c += minFlow;

             }

             minCost += dis[T] * minFlow;

         }

         return minCost;

     }

     void build(int nt, int kt)

     {

         int nnt = nt * nt;

         init(nnt *  + );

         int val[][], height[][];

         memset(val, 0x3f, sizeof(val));

         memset(height, 0x3f, sizeof(height));

         for (int i = ; i <= nt; ++i)

             for (int j = ; j <= nt; ++j)

                 scanf("%d", &val[i][j]);

         for (int i = ; i <= nt; ++i)

             for (int j = ; j <= nt; ++j)

                 scanf("%d", &height[i][j]);

         for (int i = ; i <= nt; ++i)

             for (int j = ; j <= nt; ++j)

             {

                 int pos = nt * (i - ) + j;

                 addEdge(, pos, inf, );

                 addEdge(pos, pos + nnt, ,-val[i][j]);

                 addEdge(pos, pos + nnt, inf,);

                 if (i ==  || i == nt || j ==  || j == nt)

                     addEdge(pos + nnt, n, inf, );

                 if (height[i][j] > height[i][j - ])

                     addEdge(pos + nnt, pos - , inf, );

                 if (height[i][j] > height[i][j + ])

                     addEdge(pos + nnt, pos + , inf, );

                 if (height[i][j] > height[i - ][j])

                     addEdge(pos + nnt, pos - nt, inf, );

                 if (height[i][j] > height[i + ][j])

                     addEdge(pos + nnt, pos + nt, inf, );

             }

     }

     void solve(int nt, int kt)

     {

         build(nt, kt);

         printf("%d\n", - mcmf(, n, kt));

     }

 }my;

 int main()

 {

     int tcase, n, k;

     scanf("%d", &tcase);

     while (tcase--)

     {

         scanf("%d%d", &n, &k);

         my.solve(n, k);

     }

     return ;

 }