问题描述
MF城建立在一片高原上。由于城市唯一的水源是位于河谷地带的湖中，人们在坡地上修筑了一片网格状的抽水水管，以将湖水抽入城市。如下图所示：
这片管网由 n 行 m 列节点（红色，图中 n = 5，m = 6），横向管道（紫色）和纵向管道（橙色）构成。
行和列分别用 1 到 n 的整数和 1 到 m 的整数表示。第 1 行的任何一个节点均可以抽取湖水，湖水到达第 n 行的任何一个节点即算作引入了城市。
除第一行和最后一行外，横向相邻或纵向相邻的两个节点之间一定有一段管道，每一段管道都有各自的最大的抽水速率，并需要根据情况选择抽水还是放水。对于纵向的管道（橙色），允许从上方向下方抽水或从下方向上方放水；如果从图中的上方向下方抽水，那么单位时间内能通过的水量不能超过管道的最大速率；如果从下方向上方放水，因为下方海拔较高，因此可以允许有任意大的水量。对于横向的管道（紫色），允许从左向右或从右向左抽水，不允许放水，两种情况下单位时间流过的水量都不能超过管道的最大速率。
现在MF城市的水务负责人想知道，在已知每个管道单位时间容量的情况下，MF城每单位时间最多可以引入多少的湖水。
输入格式
由于输入规模较大，我们采用伪随机生成的方式生成数据。
每组数据仅一行包含 6 个非负整数 n, m, A, B, Q, X0。其中，n 和 m 如前文所述，表示管网的大小，保证 2 ≤ n, m ≤ 5000；保证 1 ≤ A, B, Q, X0 ≤ 109。
A, B, Q, X0 是数据生成的参数，我们用如下的方式定义一个数列 { 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
样例输出
38
样例说明
使用参数得到数列 { Xi }={ 7, 16, 11, 18, 12, 9, 17, 2, 4, … }，按照输入格式可以得到每个管道的最大抽水量如下图所示：
在标准答案中，单位时间可以引水 38 单位。所有纵向管道均向下抽水即可，不需要横向管道抽水，也不需要向上放水。
样例输入
2 5 595829232 749238243 603779819 532737791
样例输出
1029036148
样例输入
5 2 634932890 335818535 550589587 977780683
样例输出
192923706
样例输入
5 5 695192542 779962396 647834146 157661239
样例输出
1449991168
EK算法，BFS（50分）：
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>
using namespace std;
long long N, M, A, B, Q, X;
queue<int> q;
//输出下一个X
long long min(long long x, long long y)
{
if (x > y)
{
return y;
}
else return x;
}
struct Edge
{
int v;//v为连接到的点，w为最大流量
long long w;
Edge(int _v, int _w) :v(_v), w(_w) {}
};
long long nextX()
{
return (A*X + B) % Q;
}
long long BFS(vector<vector<Edge> > &rgraph, int sta, int des, int pre[], int vertexNum)
{
long long *flow = new long long[vertexNum];//记录源点到每个点的最大流量
for (int i = 0; i<vertexNum; i++)
{
flow[i] = 0;
}
while (!q.empty())
{
q.pop();//清空队列
}
for (int i = 0; i<vertexNum; i++)
{
pre[i] = -1;//所有前驱节点先置为-1
}
pre[sta] = -2;//根节点前驱置为0；
flow[sta] = INT_MAX;//根节点流量置为MAX
q.push(sta);
while (!q.empty())//队列不空
{
int index = q.front();
q.pop();//取头结点
for (int i = 0; i < rgraph[index].size(); i++)
{
if (rgraph[index][i].v != sta&&rgraph[index][i].w > 0 && pre[rgraph[index][i].v] == -1)
{
pre[rgraph[index][i].v] = index;
flow[rgraph[index][i].v] = min(flow[index], rgraph[index][i].w);
q.push(rgraph[index][i].v);
}
}
}
if (pre[des] == -1)
{
return -1;
}
else
{
return flow[des];
}
}
long long EK(vector<vector<Edge> > &rgraph, int sta, int des, int pre[], int vertexNum)
{
long long increase = 0;//增量
long long sumflow = 0;
while ((increase = BFS(rgraph, sta, des, pre, vertexNum)) != -1)
{
//使用前驱寻找路径
int k = des;
while (k != sta)//不到起点就循环
{
int last = pre[k];//上一个节点
int mark;//用来标记上一条边
int i;
for (i = 0; i < rgraph[last].size(); i++)
{
if (rgraph[last][i].v == k)
{
mark = i;
break;
}
}
if (rgraph[last][mark].w != INT_MAX)
{
rgraph[last][mark].w -= increase;
}
mark = -1;
for (i = 0; i < rgraph[k].size(); i++)
{
if (rgraph[k][i].v == last)
{
mark = i;
break;
}
}
if (mark != -1)
{
if (rgraph[k][mark].w != INT_MAX)
{
rgraph[k][mark].w += increase;
}
}
k = last;
}
sumflow += increase;
}
return sumflow;
}
int main()
{
cin >> N >> M >> A >> B >> Q >> X;
//建图
//令0为超源点，1为超汇点，所以其他的点全部加2
int offset = 2;
int vertexNum = N*M + 2;//点的总数，包括超源点和超汇点
vector<vector<Edge> > gragh(vertexNum, vector<Edge>());//二维向量储存图
//存储纵边
for (int n = 0; n < N - 1; n++)
{
for (int m = 0; m < M; m++)
{
int from = n*M + m + offset;//第n+1行，第m个
int to = from + M;//第n+2行，第m个
X = nextX();//初始X为X0，计算下一个X
gragh[from].push_back(Edge(to, X));
gragh[to].push_back(Edge(from, X));
}
}
//储存横边
for (int n = 1; n < N - 1; n++)
{
for (int m = 0; m < M - 1; m++)
{
int from = n*M + m + offset;//第n+1行，第m个
int to = from + 1;//第n+1行，第m+1个
X = nextX();//初始X为X0，计算下一个X
gragh[from].push_back(Edge(to, X));
gragh[to].push_back(Edge(from, X));
}
}
//储存超源点向河边的边
for (int m = 0; m < M; m++)
{
int from = 0;
int to = m + offset;
gragh[from].push_back(Edge(to, INT_MAX));
}
//储存城市边到超汇点的边
for (int m = 0; m < M; m++)
{
int from = (N - 1)*M + m + offset;
int to = 1;
gragh[from].push_back(Edge(to, INT_MAX));
}
//初始化最大流量
int max = 0;
//初始化源点到每个点的最大流量
int *pre = new int[vertexNum];//记录每个点的前驱节点
cout << EK(gragh, 0, 1, pre, vertexNum);
return 0;
}dinic算法（40分）：
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>
#include<string.h>
#include<cstdio>
using namespace std;
long long N, M, A, B, Q, X;
int dep[5000];//记录点的层数
queue<int> q;
//输出下一个X
long long min(long long x, long long y)
{
if (x > y)
{
return y;
}
else return x;
}
struct Edge
{
int v;//v为连接到的点，w为最大流量
long long w;
Edge(int _v, int _w):v(_v), w(_w){}
};
long long nextX()
{
return (A*X + B) % Q;
}
long long BFS(vector<vector<Edge> > &rgraph, int sta, int des)
{
queue<int> q;
while (!q.empty())
{
q.pop();
}
memset(dep, -1, sizeof(dep));
dep[sta] = 0;
q.push(sta);
while (!q.empty())
{
int index = q.front();
q.pop();
for (int i = 0; i < rgraph[index].size(); i++)
{
if (rgraph[index][i].w > 0 && dep[rgraph[index][i].v] == -1)
{
dep[rgraph[index][i].v] = dep[index] + 1;
q.push(rgraph[index][i].v);
}
}
}
return dep[des] != -1;
}
long long DFS(vector<vector<Edge> > &rgraph, int sta, int des,int m)
{
if (sta == des)
return m;
int temp;
for (int i = 0; i < rgraph[sta].size(); i++)
{
if (rgraph[sta][i].w > 0 && dep[rgraph[sta][i].v] == dep[sta] + 1 && (temp = DFS(rgraph,rgraph[sta][i].v,des, min(m, rgraph[sta][i].w))))
{
long long before = rgraph[sta][i].w;
if (rgraph[sta][i].w != INT_MAX)
{
rgraph[sta][i].w -= temp;
}
int mark =-1;
//找到当前点在指向的点中i的值
for (int j = 0; j < rgraph[rgraph[sta][i].v].size(); j++)
{
if (rgraph[rgraph[sta][i].v][j].v == sta)
{
mark = j;
break;
}
}
if (mark != -1)
{
if (rgraph[rgraph[sta][i].v][mark].w != INT_MAX)
{
long long before = rgraph[rgraph[sta][i].v][mark].w;
rgraph[rgraph[sta][i].v][mark].w += temp;
}
}
return temp;
}
}
return 0;
}
long long Dinic(vector<vector<Edge> > &rgraph, int sta, int des)
{
long long increase;
long long sumflow = 0;//总量
while (BFS(rgraph, sta, des))
{
while (1)
{
increase = DFS(rgraph, sta, des, INT_MAX);
if (increase == 0)
{
break;
}
sumflow += increase;
}
}
return sumflow;
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld", &N, &M, &A, &B, &Q, &X);
//建图
//令0为超源点，1为超汇点，所以其他的点全部加2
int offset = 2;
int vertexNum = N*M + 2;//点的总数，包括超源点和超汇点
vector<vector<Edge> > gragh(vertexNum, vector<Edge>());//二维向量储存图
//存储纵边
for (int n = 0; n < N - 1; n++)
{
for (int m = 0; m < M; m++)
{
int from = n*M + m + offset;//第n+1行，第m个
int to = from + M;//第n+2行，第m个
X = nextX();//初始X为X0，计算下一个X
gragh[from].push_back(Edge(to, X));
gragh[to].push_back(Edge(from, X));
}
}
//储存横边
for (int n = 1; n < N - 1; n++)
{
for (int m = 0; m < M-1; m++)
{
int from = n*M + m + offset;//第n+1行，第m个
int to = from + 1;//第n+1行，第m+1个
X = nextX();//初始X为X0，计算下一个X
gragh[from].push_back(Edge(to, X));
gragh[to].push_back(Edge(from, X));
}
}
//储存超源点向河边的边
for (int m = 0; m < M; m++)
{
int from = 0;
int to = m + offset;
gragh[from].push_back(Edge(to, INT_MAX));
}
//储存城市边到超汇点的边
for (int m = 0; m < M; m++)
{
int from = (N - 1)*M + m + offset;
int to = 1;
gragh[from].push_back(Edge(to, INT_MAX));
}
cout << Dinic(gragh, 0, 1);
return 0;
}