P4015 运输问题【zkw费用流】

输入输出样例

输入 #1

2 3
220 280
170 120 210
77 39 105
150 186 122

输出 #1

48500
69140zuixiaofeiyo

说明/提示

$思路$

$这题不应该算是个紫题吧。。$

$没啥坑，也很容易想到最大费用流就是把所有边转换为负边权后的最小费用流$

$建图也很好想$

$CODE$

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6                    
  7 template<class T>inline void read(T &res)
  8 {
  9     char c;T flag=1;
 10     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 11     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 12 }
 13 
 14 const int MAXN = 2e3 + 5;
 15 const int inf = 0x3f3f3f3f;
 16 
 17 int N, M;
 18 
 19 namespace zkw{
 20     struct Edge{
 21         int to, val, cost;
 22         Edge *next, *ops;
 23         Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
 24     };
 25 
 26     Edge *head[MAXN << 1];
 27 
 28     void BuildGraph(int u, int v, int w, int c) {
 29         head[u] = new Edge(v, w, c, head[u]);
 30         head[v] = new Edge(u, 0, -c, head[v]);
 31         head[u]->ops = head[v]; head[v]->ops = head[u];
 32     }
 33 
 34     int s, t, ans, res;
 35     int dis[MAXN << 1];
 36     bool vis[MAXN << 1];
 37     void init() {
 38         memset(dis, 0x3f, sizeof(dis));
 39         memset(vis, false, sizeof(vis));
 40         s = 0, t = 0, ans = 0, res = 0;
 41     }
 42     bool Spfa() {
 43         memset(vis, false, sizeof vis);
 44         memset(dis, 0x3f, sizeof dis);
 45         deque<int> q;
 46         q.push_back(s);
 47         vis[s] = true; dis[s] = 0;
 48         while (!q.empty()) {
 49             int u = q.front(); q.pop_front(); vis[u] = false;
 50             for (Edge *e = head[u]; e; e = e->next) {
 51                 int v = e->to;
 52                 if (e->val > 0 && dis[u] + e->cost < dis[v]) {
 53                     dis[v] = dis[u] + e->cost;
 54                     if (!vis[v]) {
 55                         vis[v] = true;
 56                         if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
 57                         else q.push_back(v);
 58                     }
 59                 }
 60             }
 61         }
 62         return dis[t] < inf;
 63     }
 64 
 65     int Dfs(int u, int flow) {
 66         if (u == t) {
 67             vis[u] = true;
 68             res += flow;
 69             return flow;
 70         }
 71         int used = 0; vis[u] = true;
 72         for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
 73             int v = e->to;
 74             if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
 75                 int mi = Dfs(v, min(e->val, flow - used));
 76                 if (mi) {
 77                     e->val -= mi;
 78                     e->ops->val += mi;
 79                     ans += e->cost * mi;
 80                     used += mi;
 81                 }
 82                 if (used == flow) break;
 83             }
 84         }
 85         return used;
 86     }
 87 
 88     void Work() {
 89         res = 0; ans = 0;
 90         while (Spfa()) {
 91             vis[t] = true;
 92             while (vis[t]) {
 93                 memset(vis, false, sizeof vis);
 94                 Dfs(s, inf);
 95             }
 96         }
 97     }
 98 }
 99 
100 namespace zkw2{
101     struct Edge{
102         int to, val, cost;
103         Edge *next, *ops;
104         Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
105     };
106 
107     Edge *head[MAXN << 1];
108 
109     void BuildGraph(int u, int v, int w, int c) {
110         head[u] = new Edge(v, w, c, head[u]);
111         head[v] = new Edge(u, 0, -c, head[v]);
112         head[u]->ops = head[v]; head[v]->ops = head[u];
113     }
114 
115     int s, t, ans, res;
116     int dis[MAXN << 1];
117     bool vis[MAXN << 1];
118     void init() {
119         memset(dis, 0x3f, sizeof(dis));
120         memset(vis, false, sizeof(vis));
121         s = 0, t = 0, ans = 0, res = 0;
122     }
123     bool Spfa() {
124         memset(vis, false, sizeof vis);
125         memset(dis, 0x3f, sizeof dis);
126         deque<int> q;
127         q.push_back(s);
128         vis[s] = true; dis[s] = 0;
129         while (!q.empty()) {
130             int u = q.front(); q.pop_front(); vis[u] = false;
131             for (Edge *e = head[u]; e; e = e->next) {
132                 int v = e->to;
133                 if (e->val > 0 && dis[u] + e->cost < dis[v]) {
134                     dis[v] = dis[u] + e->cost;
135                     if (!vis[v]) {
136                         vis[v] = true;
137                         if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
138                         else q.push_back(v);
139                     }
140                 }
141             }
142         }
143         return dis[t] < inf;
144     }
145 
146     int Dfs(int u, int flow) {
147         if (u == t) {
148             vis[u] = true;
149             res += flow;
150             return flow;
151         }
152         int used = 0; vis[u] = true;
153         for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
154             int v = e->to;
155             if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
156                 int mi = Dfs(v, min(e->val, flow - used));
157                 if (mi) {
158                     e->val -= mi;
159                     e->ops->val += mi;
160                     ans += e->cost * mi;
161                     used += mi;
162                 }
163                 if (used == flow) break;
164             }
165         }
166         return used;
167     }
168 
169     void Work() {
170         res = 0; ans = 0;
171         while (Spfa()) {
172             vis[t] = true;
173             while (vis[t]) {
174                 memset(vis, false, sizeof vis);
175                 Dfs(s, inf);
176             }
177         }
178     }
179 }
180 
181 
182 int a[207], b[207];
183 int val[207][207];
184 int val2[207][207];
185 
186 signed main() {
187     read(M);
188     read(N);
189     zkw::init();
190     zkw :: s = 0; zkw :: t = M + N + 1;
191     int s = 0, t = M + N + 1;
192     for ( int i = 1; i <= M; ++i ) {
193         read(a[i]);
194         zkw::BuildGraph(s, i, a[i], 0);
195     }
196     for ( int i = 1; i <= N; ++i ) {
197         read(b[i]);
198         zkw::BuildGraph(i + M, t, b[i], 0);
199     }
200     for ( int i = 1; i <= M; ++i ) {
201         for ( int j = 1; j <= N; ++j ) {
202             read(val[i][j]);
203             val2[i][j] = -val[i][j];
204             zkw::BuildGraph(i, j + M, inf, val[i][j]);
205         }
206     }
207     zkw :: Work();
208     cout << zkw::ans << endl;
209     zkw2::init();
210     zkw2 :: s = 0; zkw2 :: t = M + N + 1;
211     s = 0, t = M + N + 1;
212     for ( int i = 1; i <= M; ++i ) {
213         zkw2::BuildGraph(s, i, a[i], 0);
214     }
215     for ( int i = 1; i <= N; ++i ) {
216         zkw2::BuildGraph(i + M, t, b[i], 0);
217     }
218     for ( int i = 1; i <= M; ++i ) {
219         for ( int j = 1; j <= N; ++j ) {
220             zkw2::BuildGraph(i, j + M, inf, val2[i][j]);
221             //printf("u:%d v:%d val2[i][j]:%d
",i, j + M, val2[i][j]);
222         }
223     }
224     zkw2::Work();
225     cout << 0 - zkw2::ans << endl;
226     return 0;
227 }

View Code

#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl

using namespace std;
typedef long long LL;
                   
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

const int MAXN = 2e3 + 5;
const int inf = 0x3f3f3f3f;

int N, M;

namespace zkw{
    struct Edge{
        int to, val, cost;
        Edge *next, *ops;
        Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
    };

    Edge *head[MAXN << 1];

    void BuildGraph(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    int s, t, ans, res;
    int dis[MAXN << 1];
    bool vis[MAXN << 1];
    void init() {
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, false, sizeof(vis));
        s = 0, t = 0, ans = 0, res = 0;
    }
    bool Spfa() {
        memset(vis, false, sizeof vis);
        memset(dis, 0x3f, sizeof dis);
        deque<int> q;
        q.push_back(s);
        vis[s] = true; dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front(); vis[u] = false;
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (e->val > 0 && dis[u] + e->cost < dis[v]) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
        return dis[t] < inf;
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            vis[u] = true;
            res += flow;
            return flow;
        }
        int used = 0; vis[u] = true;
        for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
            int v = e->to;
            if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                    used += mi;
                }
                if (used == flow) break;
            }
        }
        return used;
    }

    void Work() {
        res = 0; ans = 0;
        while (Spfa()) {
            vis[t] = true;
            while (vis[t]) {
                memset(vis, false, sizeof vis);
                Dfs(s, inf);
            }
        }
    }
}

namespace zkw2{
    struct Edge{
        int to, val, cost;
        Edge *next, *ops;
        Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
    };

    Edge *head[MAXN << 1];

    void BuildGraph(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    int s, t, ans, res;
    int dis[MAXN << 1];
    bool vis[MAXN << 1];
    void init() {
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, false, sizeof(vis));
        s = 0, t = 0, ans = 0, res = 0;
    }
    bool Spfa() {
        memset(vis, false, sizeof vis);
        memset(dis, 0x3f, sizeof dis);
        deque<int> q;
        q.push_back(s);
        vis[s] = true; dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front(); vis[u] = false;
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (e->val > 0 && dis[u] + e->cost < dis[v]) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
        return dis[t] < inf;
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            vis[u] = true;
            res += flow;
            return flow;
        }
        int used = 0; vis[u] = true;
        for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
            int v = e->to;
            if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                    used += mi;
                }
                if (used == flow) break;
            }
        }
        return used;
    }

    void Work() {
        res = 0; ans = 0;
        while (Spfa()) {
            vis[t] = true;
            while (vis[t]) {
                memset(vis, false, sizeof vis);
                Dfs(s, inf);
            }
        }
    }
}


int a[207], b[207];
int val[207][207];
int val2[207][207];

signed main() {
    read(M);
    read(N);
    zkw::init();
    zkw :: s = 0; zkw :: t = M + N + 1;
    int s = 0, t = M + N + 1;
    for ( int i = 1; i <= M; ++i ) {
        read(a[i]);
        zkw::BuildGraph(s, i, a[i], 0);
    }
    for ( int i = 1; i <= N; ++i ) {
        read(b[i]);
        zkw::BuildGraph(i + M, t, b[i], 0);
    }
    for ( int i = 1; i <= M; ++i ) {
        for ( int j = 1; j <= N; ++j ) {
            read(val[i][j]);
            val2[i][j] = -val[i][j];
            zkw::BuildGraph(i, j + M, inf, val[i][j]);
        }
    }
    zkw :: Work();
    cout << zkw::ans << endl;
    zkw2::init();
    zkw2 :: s = 0; zkw2 :: t = M + N + 1;
    s = 0, t = M + N + 1;
    for ( int i = 1; i <= M; ++i ) {
        zkw2::BuildGraph(s, i, a[i], 0);
    }
    for ( int i = 1; i <= N; ++i ) {
        zkw2::BuildGraph(i + M, t, b[i], 0);
    }
    for ( int i = 1; i <= M; ++i ) {
        for ( int j = 1; j <= N; ++j ) {
            zkw2::BuildGraph(i, j + M, inf, val2[i][j]);
            //printf("u:%d v:%d val2[i][j]:%d
",i, j + M, val2[i][j]);
        }
    }
    zkw2::Work();
    cout << 0 - zkw2::ans << endl;
    return 0;
}