Skip to content

14050: 【原4050】girls

题目

题目描述

author: Kodak 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4050 

Description

军训期间,23连小姐姐排成了N*M的矩阵正在走正步,而面包包则暗中观察给每个小姐姐打了一个分数。

没错,面包包打算晚上联谊的时候找小姐姐们要联系方式,这是在为下一步的行动打下基础。

但是白天走正步的时候小姐姐们会和自己前后左右的人交流。如果两个小姐姐交流的时候发现面包包同时要了她们两个的联系方式,没有小机机那样同时和两个小姐姐谈笑风生能力的面包包就会GG。

所以他打算晚上只要一部分小姐姐的联系方式,剩下的从同学那旁敲侧击。由于同学那拿来的联系方式并不一定靠谱,面包包希望他直接要到联系方式的小姐姐分数总和能尽可能的高。

Input Format

第一行两个数N,M (N,M <= 100)

之后N行,每行M个数,为面包给对应位置小姐姐打的分

Output Format

一个数Ans, 面包包直接要到联系方式的小姐姐分数总和

Sample Input

2 2
100 99
60 0

Sample Output

159

zqy2018's solution

/*
    Hint: use network flow
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, a[105][105];
int to[100005], cap[100005], nxt[100005], at[10005], cnt = 0;
int flow[100005] = {0}, cur[100005] = {0}, d[10005] = {0};
int pos[10005] = {0};
bool vis[10005] = {0}, isleft[10005] = {0};
queue<int> q;
int S, T;
inline void addedge(int u_, int v_, int c_){
    if (!isleft[u_]) swap(u_, v_);
    to[cnt] = v_, nxt[cnt] = at[u_], cap[cnt] = c_, at[u_] = cnt++;
    to[cnt] = u_, nxt[cnt] = at[v_], cap[cnt] = 0, at[v_] = cnt++;
}
bool bfs(){
    memset(vis, 0, sizeof(vis));
    q.push(S);
    d[S] = 0, vis[S] = true;
    while (!q.empty()){
        int h = q.front();
        q.pop();
        for (int i = at[h]; i != -1; i = nxt[i]){
            if (!vis[to[i]] && cap[i] > flow[i])
                vis[to[i]] = true, 
                d[to[i]] = d[h] + 1,
                q.push(to[i]);
        }
    }
    return vis[T];
}
int dfs(int u, int f){
    if (u == T || f == 0) return f;
    int now_flow = 0, fl;
    for (int &i = cur[u]; i != -1; i = nxt[i]){
        if (d[to[i]] == d[u] + 1 && (fl = dfs(to[i], min(f, cap[i] - flow[i]))) > 0){
            flow[i] += fl, flow[i ^ 1] -= fl;
            now_flow += fl, f -= fl;
            if (!f) break;
        }
    }
    return now_flow;
}
int dinic(){
    int max_flow = 0, ans;
    while (bfs()){
        for (int i = 0; i <= n * m + 1; ++i)
            cur[i] = at[i];
        max_flow += dfs(S, INF);
    }
    return max_flow;
}
void init(){
    n = read(), m = read();
    int tot = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[i][j] = read();
    for (int i = 1; i <= n; ++i)
        for (int j = (i & 1 ? 1: 2); j <= m; j += 2)
            isleft[(i - 1) * m + j] = true;
    memset(at, -1, sizeof(at));
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            if (i < n) addedge((i - 1) * m + j, i * m + j, INF);
            if (j < m) addedge((i - 1) * m + j, (i - 1) * m + j + 1, INF);
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j){
            int id = (i - 1) * m + j;
            if (isleft[id]) 
                to[cnt] = id, nxt[cnt] = at[0], cap[cnt] = a[i][j], at[0] = cnt++,
                to[cnt] = 0, nxt[cnt] = at[id], cap[cnt] = 0, at[id] = cnt++;
            else 
                to[cnt] = n * m + 1, nxt[cnt] = at[id], cap[cnt] = a[i][j], at[id] = cnt++,
                to[cnt] = id, nxt[cnt] = at[n * m + 1], cap[cnt] = 0, at[n * m + 1] = cnt++;
        }
    S = 0, T = n * m + 1;
}
void solve(){
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)    
            sum += a[i][j];
    printf("%d\n", sum - dinic());
}
int main(){
    init();
    solve();
    return 0;
}