【CCF CSP 2017-03-15】【Hard】引水入城II 动态规划

古城微笑少年丶 2023-06-03 15:54 8阅读 0赞

MF城建立在一片高原上。由于城市唯一的水源是位于河谷地带的湖中，人们在坡地上修筑了一片网格状的抽水水管，以将湖水抽入城市。如下图所示：  
![891812-20190920171028657-1651428467.png][]  
  
  
　　这片管网由 *n* 行 *m* 列节点（红色，图中 *n* = 5， *m* = 6），横向管道（紫色）和纵向管道（橙色）构成。  
　　行和列分别用 1 到 *n* 的整数和 1 到 *m* 的整数表示。第 1 行的任何一个节点均可以抽取湖水，湖水到达第 *n* 行的任何一个节点即算作引入了城市。  
　　除第一行和最后一行外，横向相邻或纵向相邻的两个节点之间一定有一段管道，每一段管道都有各自的最大的抽水速率，并需要根据情况选择抽水还是放水。对于纵向的管道（橙色），允许从上方向下方抽水或从下方向上方放水；如果从图中的上方向下方抽水，那么单位时间内能通过的水量不能超过管道的最大速率；如果从下方向上方放水，因为下方海拔较高，因此可以允许有任意大的水量。对于横向的管道（紫色），允许从左向右或从右向左抽水，不允许放水，两种情况下单位时间流过的水量都不能超过管道的最大速率。  
　　现在MF城市的水务负责人想知道，在已知每个管道单位时间容量的情况下，MF城每单位时间最多可以引入多少的湖水。

**输入格式**

由于输入规模较大，我们采用伪随机生成的方式生成数据。  
　　每组数据仅一行包含 6 个非负整数 *n*, *m*, *A*, *B*, *Q*, *X* 0。其中， *n* 和 *m* 如前文所述，表示管网的大小，保证 2 ≤ *n*, *m* ≤ 5000；保证 1 ≤ *A*, *B*, *Q*, *X* 0 ≤ 10 9。  
　　 *A*, *B*, *Q*, *X* 0 是数据生成的参数，我们用如下的方式定义一个数列 \{ *Xi* \}：  
　　 *Xi* \+1 = ( *AXi* \+ *B*) **mod** *Q*, ( *i* ≥ 0)  
　　我们将数列的第 1 项到第 ( *n*\-1) *m* 项作为纵向管道的单位时间容量，其中 *X* (*s*\-1)*m*\+*t* 表示第 *s* 行第 *t* 列的节点到第 *s*\+1 行第 *t* 列管道单位时间的容量；将数列的第 ( *n*\-1) *m*\+1 项到第 ( *n*\-1) *m*\+ **(*n*\-2)(*m*\-1)** 项（即接下来的 ( *n*\-2)( *m*\-1) 项）作为横向管道的单位时间容量，其中 *X* (*n*\-1)*m*\+**(*s*\-2)(*m*\-1)**\+*t* 表示第 *s* 行第 *t* 列的节点到第 *s* 行第 *t*\+1 列管道单位时间的容量。

**输出格式**

输出一行一个整数，表示MF城每单位时间可以引入的水量。  
　　注意计算过程中有些参数可能超过32位整型表示的最大值，请注意使用64位整型存储相应数据。

**样例输入**

3 3 10 3 19 7

**样例输出**

**样例说明**

使用参数得到数列 \{ *Xi* \}=\{ 7, 16, 11, 18, 12, 9, 17, 2, 4, … \}，按照输入格式可以得到每个管道的最大抽水量如下图所示：  
![891812-20190920171119388-2037668818.png][]

在标准答案中，单位时间可以引水 38 单位。所有纵向管道均向下抽水即可，不需要横向管道抽水，也不需要向上放水。

**样例输入**

2 5 595829232 749238243 603779819 532737791

**样例输出**

1029036148

**样例输入**

5 2 634932890 335818535 550589587 977780683

**样例输出**

192923706

**样例输入**

5 5 695192542 779962396 647834146 157661239

**样例输出**

1449991168

**评测用例规模与约定**

共有10组评测数据，每组数据的参数规模如下所示：

<table> 
 <tbody> 
  <tr> 
   <td>测试点编号</td> 
   <td><em>n</em></td> 
   <td><em>m</em></td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>=2</td> 
   <td>=1000</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>=1000</td> 
   <td>=2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>=1000</td> 
   <td>=2</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>=5</td> 
   <td>=5</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>=10</td> 
   <td>=10</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>=100</td> 
   <td>=100</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>=500</td> 
   <td>=500</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>=1000</td> 
   <td>=1000</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>=2000</td> 
   <td>=2000</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>=5000</td> 
   <td>=5000</td> 
  </tr> 
 </tbody> 
</table>

**评测题解**

这个题目也叫引水入城, 参考之前的引水入城I. [https://www.cnblogs.com/wangzming/p/11466611.html][https_www.cnblogs.com_wangzming_p_11466611.html]

与之前的题目不同，之前的传输是以方格为单位，相邻的格子传输的,

而当前的传输就是点到点，方格本身不是城市。

根据这个题目的信息，也许可以用Ford-Fulkerson/Dicnic/EK算法求最大流，很可惜这个题目是反套路的，

因为它的结构太规整了，以至于不需要建图求最大流。另外它的边数大概是E=O(2 \* V)，O(VE)达到了计算上限。

用动态规划，求每条边受到的限制，最后也是用动态规划（其实就是计算有约束的最小值的和）。

#pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    #include <cstdio>
    const int maxn = 5000;
    const long long inf = 0x3f3f3f3f3f3f3f3fLL;
    int n,m,A,B,Q,X0,col[maxn][maxn],row[maxn][maxn];
    long long dp[maxn],v;
    int main()
    {
        scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&Q,&X0);
        // build the graph
        for (int i = 0; i < n - 1; ++i)
            for (int j = 0; j < m; ++j)
                col[j][i] = X0 = ((long long)A*X0+B)%Q;
        for (int i = 1; i <= n - 2; ++i)
            for (int j = 0; j < m - 1; ++j)
                row[j][i] = X0 = ((long long)A*X0+B)%Q;
        /* the graph is marked as:
        cols: |    |    |    |    (i,j) = (0... n - 1, 0...m-1)
        rows:  ____ ____ ____     (i,j) = (1... n - 2, 0...m-2)
        */
        // compute the cap limit of col
        for (int i = 0; i < n - 1; ++i)
            dp[i] = col[0][i];
        // the limit of col + row
        for (int i = 1; i < n - 1; ++i) {
            v = dp[i - 1] + row[0][i];
            dp[i] = dp[i] < v ? dp[i] : v;
        }
        for (int i = n - 3; i >= 0;--i) {
            v = dp[i + 1] + row[0][i + 1];
            dp[i] = dp[i] < v ? dp[i] : v;
        }
        // the sum of each col(with limit)
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n - 1; ++j)
                dp[j] += col[i][j];
            for (int j = 1; j < n - 1; ++j) {
                v = dp[j - 1] + row[i][j];
                dp[j] = dp[j] < v ? dp[j] : v;
            }
            for (int j = n - 3; j >= 0; --j) {
                v = dp[j + 1] + row[i][j + 1];
                dp[j] = dp[j] < v ? dp[j] : v;
            }
        }
        long long res = inf;
        for (int i = 0; i < n - 1; ++i)
            res = res < dp[i] ? res : dp[i];
        printf("%I64d\n",res);
        return 0;
    }

**References:**

CCF认证系统 [http://118.190.20.162/view.page?gpid=T53][http_118.190.20.162_view.page_gpid_T53]

CCF CSP 201703-5 引水入城 (100分) [https://blog.csdn.net/u013944294/article/details/79620059][https_blog.csdn.net_u013944294_article_details_79620059]

转载于:https://www.cnblogs.com/wangzming/p/11558367.html

[891812-20190920171028657-1651428467.png]: /images/20230601/105a756c1645450980d8026b94b7af24.png
[891812-20190920171119388-2037668818.png]: /images/20230601/bc2ecb2f75484ce8b71b1e5346f04d91.png
[https_www.cnblogs.com_wangzming_p_11466611.html]: https://www.cnblogs.com/wangzming/p/11466611.html
[http_118.190.20.162_view.page_gpid_T53]: http://118.190.20.162/view.page?gpid=T53
[https_blog.csdn.net_u013944294_article_details_79620059]: https://blog.csdn.net/u013944294/article/details/79620059