CCF 引水入城

小鱼儿 2021-06-24 15:58 272阅读 0赞

## **一、试题** ##

问题描述  
　　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  
评测用例规模与约定  
　　共有10组评测数据，每组数据的参数规模如下所示：  
测试点编号  
n  
m  
1  
=2  
=1000  
2  
=1000  
=2  
3  
=1000  
=2  
4  
=5  
=5  
5  
=10  
=10  
6  
=100  
=100  
7  
=500  
=500  
8  
=1000  
=1000  
9  
=2000  
=2000  
10  
=5000  
=5000

## **二、代码** ##

这一题是最大流最小割问题，需要湖作为源，城市作为汇。但由于有多个源点和多个汇点，所以需要建一个超级源点和超级汇点。  
他人50代码：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <utility>
    #include <climits>
    
    using namespace std;
    
    long long A, B, Q, X;
    int numVertex;
    
    int nextRandom() {
        X = (A * X + B) % Q;
        return X;
    }
    
    struct Edge {
        int v; // vertex
        int w; // weight
        Edge(int v_, int w_) : v(v_), w(w_) {}
    };
    
    bool bfs(vector<vector<Edge> > &rgraph, int s, int t, vector<pair<int,int> > &parents) {
        queue<int> q;
        vector<bool> visited(numVertex);
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i=0; i<rgraph[u].size(); i++) {
                int v = rgraph[u][i].v;
                if(!visited[v] && rgraph[u][i].w>0) {
                    visited[v] = true;
                    parents[v] = make_pair(u,i);
                    q.push(v);
                    if(v == t) return true;
                }
    
            }
        }
        return false;
    }
    
    long long fordFulkerson(vector<vector<Edge> > &rgraph, int s, int t) {
        long long maxFlow = 0;
        vector<pair<int,int> > parents(numVertex);
        while(bfs(rgraph, 0, 1, parents)) {
            int pathFlow = INT_MAX;
            for(int v=t; v!=s; ) {
                int u=parents[v].first;
    
                int ui = parents[v].second;
                pathFlow = min(pathFlow, rgraph[u][ui].w);
                v = u;
            }
            maxFlow += pathFlow;
    // cout << pathFlow << " " << maxFlow << endl;
            for(int v=t; v!=s; ) {
                int u = parents[v].first;
                int ui = parents[v].second;
                if(rgraph[u][ui].w!=INT_MAX) rgraph[u][ui].w -= pathFlow;
                int vi = -1;
                for(int i=0; i<rgraph[v].size(); i++) {
                    if(rgraph[v][i].v == u) {
                        vi = i;
                    }
                }
                if(vi!=-1 && rgraph[v][vi].w!=INT_MAX) rgraph[v][vi].w += pathFlow;
                v = u;
            }
        }
        return maxFlow;
    }
    
    int main() {
        int N, M;
        cin >> N >> M >> A >> B >> Q >> X;
        numVertex = N * M + 2;
        // 0:source, 1:sink, 
        vector<vector<Edge> > graph(numVertex, vector<Edge>());
    
        int offset = 2;
        // construct graph
        for(int n=0; n<N-1; n++) {
            for(int m=0; m<M; m++) {
                int from = n*M+m+offset;
                int to = from+M;
                nextRandom();
                graph[from].push_back(Edge(to, X));
                graph[to].push_back(Edge(from, INT_MAX));
            }
        }
    
        for(int m=0; m<M; m++) {
            int from = 0;
            int to = m+offset;
            graph[from].push_back(Edge(to, INT_MAX));
        }
    
        for(int m=0; m<M; m++) {
            int from = (N-1)*M+m+offset;
            int to = 1;
            graph[from].push_back(Edge(to, INT_MAX));
        }
    
        long long maxFlow = 0;
    
        for(int n=1; n<N-1; n++) {
            for(int m=0; m<M-1; m++) {
                int from = n*M+m+offset;
                int to = from+1;
                nextRandom();
                graph[from].push_back(Edge(to, X));
                graph[to].push_back(Edge(from, X));
            }
        }
    
        maxFlow += fordFulkerson(graph, 0, 1);
    
        cout << maxFlow;
    }

运行错误代码：

#include<iostream>
    #include<vector>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    typedef long long LL; 
    
    struct Node{
        int to;
        int cap;
        int rev;
        Node(int a, int b, int c):to(a),cap(b),rev(c){}
    };
    
    const int MAX = 25000010;
    const int INF = 0x3f3f3f3f;
    
    vector<Node> v[MAX];
    bool used[MAX];
    
    int  dfs(int s,int t,int f)  
    {  
        if(s==t)  
            return f;  
        used[s]=true;  
        for(int i=0;i<v[s].size();i++)  
        {  
            Node &tmp = v[s][i];  //注意 
            if(used[tmp.to]==false && tmp.cap>0)  
            {  
                int d=dfs(tmp.to,t,min(f,tmp.cap));  
                if(d>0)  
                {   
                    if(tmp.cap != INF){
                        tmp.cap-=d;
                    }
    
                    if(v[tmp.to][tmp.rev].cap != INF){
                        v[tmp.to][tmp.rev].cap+=d;
                    } 
    
                    return d;  
                }  
            }  
        }  
        return 0;  
    }  
    
    LL max_flow(int s,int t)  
    {  
        LL flow=0;  
        for(;;){  
            memset(used,false,sizeof(used));  
            int f=dfs(s,t,INF);  
            if(f==0)  
                return flow;  
            flow+=f;  
        }  
    }  
    
    
    int main(){
        int n, m;
        LL A, B, Q, X0;
        cin>>n>>m>>A>>B>>Q>>X0;
        long long X = X0;
    
        for(int i=0; i<n-1; i++){
            for(int j=0; j<m; j++){
                X = (A*X+B)%Q;
                int from = i*m+j<m?0:i*m+j;
                int to = i*m+j+m>(n-1)*m-1?n*m:i*m+j+m;
    // v[to].size()记录了从to到from路径在V中存储的index，也就是第二步添加的位置 
    // v[from].size()-1记录了从from到to路径在v中存储的index，也就是第一步添加的位置 
    // v[from].push_back((Node){to, X, v[to].size()}); /*第一步*/ 
    // v[to].push_back((Node){from, INF , v[from].size()-1}); /*第二步*/
                v[from].push_back(Node(to, X, v[to].size()) );   /*第一步*/ 
                v[to].push_back( Node(from, INF , v[from].size()-1) );  /*第二步*/
    // cout<<from<<" "<<to<<" "<<X<<"@"<<endl; 
            }
        }
        for(int i=1; i<n-1; i++){
            for(int j=0; j<m-1; j++){
                X = (A*X+B)%Q;
                int from = i*m+j;
                int to = i*m+j+1;
                v[from].push_back( Node(to, X, v[to].size()) );
                v[to].push_back( Node(from, X, v[from].size()-1) );
    // cout<<from<<" "<<to<<" "<<X<<endl; 
            }
        }
        cout<<max_flow(0,n*m);
        return 0;
    }