新建 文本文档 (5).txt

给你一个m行n列的格子的棋盘

#include <cstdio> 
#include <vector> 
#include <queue> 
#include <algorithm> 
using namespace std; 
const int N = 2500+10; 
const int INF = 1 << 28; 
const int INF2 = 1 << 20; 
class Edge { 
public: 
    int u, v, cuv, cvu, flow; 
    Edge() {} 
    Edge(int cu, int cv, int ccu, int ccv) : u(cu), v(cv), cuv(ccu), cvu(ccv), flow(0) {} 
    int other(int p) const { return p == u ? v : u; } 
    int cap(int p) const { return p == u ? cuv-flow : cvu+flow; } 
    void addFlow(int p, int f) { flow += (p == u ? f : -f); } 
}; 
class NodeList { 
private: 
    int level, next[N], index[2*N], v; 
public: 
    void clear(int cv) { v = cv; level = -1; memset(index, -1, sizeof(index)); } 
    void insert(int n, int h) { next[n] = index[h]; index[h] = n; level >?= h; } 
    int remove(); 
    bool empty() const { return level < 0; } 
}; 
int NodeList::remove() { 
    int r = index[level]; index[level] = next[index[level]]; 
    while(level >= 0 && index[level] == -1) level--; 
    return r; 
} 
class Network { 
private: 
    vector<Edge> eg; 
    vector<Edge*> net[N]; 
    int v, s, t; 
    NodeList list; 
    int h[N], hn[2*N], e[N], cur[N]; 
    void initNet(); 
    void initFlow(); 
    void initHeight(); 
    void push(int); 
    void relabel(int); 
    void discharge(int); 
    void gapHeuristic(int); 
public: 
    bool build(); 
    int maxFlow(int, int); 
}; 
void Network::gapHeuristic(int k) { 
    if(hn[k] != 0 || k >= v+1) return; 
    for(int i = 0; i < v; i++) 
        if(h[i] > k && h[i] <= v && i != s) 
            { hn[h[i]]--; hn[v+1]++; h[i] = v+1; } 
} 
void Network::initNet() { 
    for(int i = 0; i < v; i++) net[i].clear(); 
    for(int i = eg.size()-1; i >= 0; i--) { 
        net[eg[i].u].push_back(&eg[i]); 
        net[eg[i].v].push_back(&eg[i]); 
    } 
} 
void Network::initHeight() { 
    memset(h, 0, sizeof(h)); memset(hn, 0, sizeof(hn)); 
    memset(e, 0, sizeof(e)); e[s] = INF; 
    for(int i = 0; i < v; i++) h[i] = v; 
    queue<int> Q; Q.push(t); h[t] = 0; 
    while(!Q.empty()) { 
        int p = Q.front(); Q.pop(); 
        for(int i = net[p].size()-1; i >= 0; i--) { 
            int u = net[p][i]->other(p), ec = net[p][i]->cap(u); 
            if(ec != 0 && h[u] == v && u != s) { h[u] = h[p]+1; Q.push(u); } 
        } 
    } 
    for(int i = 0; i < v; i++) hn[h[i]]++; 
} 
void Network::initFlow() { 
    initNet(); initHeight(); 
    for(int i = 0; i < v; i++) cur[i] = net[i].size()-1; 
    list.clear(v); 
    for(; cur[s] >= 0; cur[s]--) push(s); 
} 
void Network::push(int u) { 
    Edge* te = net[u][cur[u]]; 
    int ex = min(te->cap(u), e[u]), p = te->other(u); 
    if(e[p] == 0 && p != t) list.insert(p, h[p]); 
    te->addFlow(u, ex); e[u] -= ex; e[p] += ex; 
} 
void Network::relabel(int u) { 
    int mh = 2*v, oh = h[u]; 
    for(int i = net[u].size()-1; i >= 0; i--) { 
        int p = net[u][i]->other(u); 
        if(net[u][i]->cap(u) != 0) mh <?= h[p]+1; 
    } 
    hn[h[u]]--; hn[mh]++; h[u] = mh; cur[u] = net[u].size()-1; 
    gapHeuristic(oh); 
} 
void Network::discharge(int u) { 
    while(e[u] > 0) 
        if(cur[u] < 0) relabel(u); 
        else if(net[u][cur[u]]->cap(u) > 0 && h[u] == h[net[u][cur[u]]->other(u)]+1) push(u); 
        else cur[u]--; 
} 
int sum;
bool Network::build() { 
    int n, m, np, nc, x, y; 
    int i, j, rec[50][50];
    if(scanf("%d%d", &n, &m)==EOF)return false;
    v = n * m + 2; eg.clear(); 
    sum = 0;
    
    for(i = 0; i < n; i ++)
        for(j = 0; j < m; j ++)
        {
            scanf("%d", &rec[i][j]);
            sum += rec[i][j];
            x = i * m + j + 2;
            if((i + j) % 2){
                eg.push_back(Edge(0, x, rec[i][j], 0));
                if( i > 0 ){
                    y = (i - 1) * m + j + 2;
                    eg.push_back(Edge(x, y, rec[i][j], 0));
                }
                if( j > 0 ){
                    y = i * m + j - 1 + 2;
                    eg.push_back(Edge(x, y, rec[i][j], 0));
                }
                if( i + 1 < n ){
                    y = (i + 1) * m + j + 2;
                    eg.push_back(Edge(x, y, rec[i][j], 0));
                }
                if( j + 1 < m ){
                    y = i * m + j + 1 + 2;
                    eg.push_back(Edge(x, y, rec[i][j], 0));
                }
            }
            else {
                eg.push_back(Edge(x, 1, rec[i][j], 0));
            }
        }
    return true; 
} 
int Network::maxFlow(int ss, int tt) { 
    s = ss; t = tt; initFlow(); 
    while(!list.empty()) { 
        int u = list.remove(); 
        discharge(u); 
    } 
    return e[t]; 
} 
int main() 
{ 
    Network net; 
    while(net.build()) printf("%d\n", sum - net.maxFlow(0, 1)); 
    return 0; 
}