深海机器人问题【网络流24题】

思路

　　和方格取数差不多的一道题

　　只是输入有点恶心

　　然而他好像提示了怎么输出

　　之后就是建图标准最大费用最大流了

　　不知道为什么spfa的最大流T了一个点

　　难道说数据这么丧心病狂吗

　　zkw的话倒是50ms就跑完了

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 struct Edge{
 20     int to, val, cost;
 21     Edge *next, *ops;
 22     Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
 23 };
 24 
 25 Edge *head[MAXN << 1];
 26 
 27 void BuildGraph(int u, int v, int w, int c) {
 28     head[u] = new Edge(v, w, c, head[u]);
 29     head[v] = new Edge(u, 0, -c, head[v]);
 30     head[u]->ops = head[v]; head[v]->ops = head[u];
 31 }
 32 
 33 namespace zkw{
 34     int s, t, ans, res;
 35     int dis[MAXN << 1];
 36     bool vis[MAXN << 1];
 37     bool Spfa() {
 38         memset(vis, false, sizeof vis);
 39         memset(dis, 0x3f, sizeof dis);
 40         deque<int> q;
 41         q.push_back(s);
 42         vis[s] = true; dis[s] = 0;
 43         while (!q.empty()) {
 44             int u = q.front(); q.pop_front(); vis[u] = false;
 45             for (Edge *e = head[u]; e; e = e->next) {
 46                 int v = e->to;
 47                 if (e->val > 0 && dis[u] + e->cost < dis[v]) {
 48                     dis[v] = dis[u] + e->cost;
 49                     if (!vis[v]) {
 50                         vis[v] = true;
 51                         if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
 52                         else q.push_back(v);
 53                     }
 54                 }
 55             }
 56         }
 57         return dis[t] < inf;
 58     }
 59 
 60     int Dfs(int u, int flow) {
 61         if (u == t) {
 62             vis[u] = true;
 63             res += flow;
 64             return flow;
 65         }
 66         int used = 0; vis[u] = true;
 67         for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
 68             int v = e->to;
 69             if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
 70                 int mi = Dfs(v, min(e->val, flow - used));
 71                 if (mi) {
 72                     e->val -= mi;
 73                     e->ops->val += mi;
 74                     ans += e->cost * mi;
 75                     used += mi;
 76                 }
 77                 if (used == flow) break;
 78             }
 79         }
 80         return used;
 81     }
 82 
 83     void Work() {
 84         res = 0; ans = 0;
 85         while (Spfa()) {
 86             vis[t] = true;
 87             while (vis[t]) {
 88                 memset(vis, false, sizeof vis);
 89                 Dfs(s, inf);
 90             }
 91         }
 92     }
 93 }
 94 
 95 int A, B, n, m;
 96 int table[20][20];
 97 int times = 0;
 98 
 99 signed main()  
100 {
101     //freopen("data.txt", "r", stdin);
102     read(A); read(B);
103     read(n); read(m);
104     for ( int i = 0; i <= n; ++i ) {
105         for ( int j = 0; j <= m; ++j ) {
106             table[i][j] = ++times;
107         }
108     }
109     int x;
110     int s, t;
111     s = 0, t = (n + 1) * (m + 1) + 1;
112     zkw::s = s, zkw::t = t;
113     for ( int i = 0; i <= n; ++i ) {
114         for ( int j = 0; j <= m - 1; ++j ) {
115             read(x);
116             BuildGraph(table[i][j], table[i][j+1], inf, 0);
117             BuildGraph(table[i][j], table[i][j + 1], 1, -x);
118         }
119     }
120     for ( int j = 0; j <= m; ++j ) {
121         for ( int i = 0; i <= n - 1; ++i ) {
122             read(x);
123             BuildGraph(table[i][j], table[i+1][j], inf, 0);
124             BuildGraph(table[i][j], table[i+1][j], 1, -x);
125         }
126     }
127     for ( int i = 1; i <= A; ++i ) {
128         int x, y, num;
129         read(num); read(x); read(y);
130         BuildGraph(s, table[x][y], num, 0);
131     }
132     for ( int i = 1; i <= B; ++i ) {
133         int x, y, num;
134         read(num); read(x); read(y);
135         //dbg(num);
136         BuildGraph(table[x][y], t, num, 0);
137     }
138     zkw::Work();
139     int ans = -zkw::ans;
140     cout << ans << endl;
141     return 0;
142 }