bzoj3894

转载自http://www.cnblogs.com/rausen

3894: 文理分科

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 1338 Solved: 760
[Submit][Status][Discuss]

Description

文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠

结过）

小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行

描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择

一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式

得到：

1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如

果选择理科，将得到science[i][j]的满意值。

2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且

仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开

心，所以会增加same_art[i][j]的满意值。

3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理

科，则增加same_science[i]j[]的满意值。

小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请

告诉他这个最大值。

Input

第一行为两个正整数：n，m

接下来n术m个整数，表示art[i][j]；

接下来n术m个整数．表示science[i][j]；

接下来n术m个整数，表示same_art[i][j]；

Output

输出为一个整数，表示最大的满意值之和

Sample Input

3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4

Sample Output

152

HINT

样例说明

1表示选择文科，0表示选择理科，方案如下：

1 0 0 1

0 1 0 0

1 0 0 0

N,M<=100,读入数据均<=500

很明显的一道网络流题。。

首先把所有值的加起来，再减掉网络流最小割值就好了，问题就是如何建图。这貌似也是考了好多次了的。。。

把每个人抽象成一个点p，则

先是S向p连边，流量为选文科的高兴值，p向T连边，流量为选理科的高兴值。

然后是same的条件，对每个人新建两个点p1, p2

S向p1连边，流量为文科same的高兴值，p1向相邻点和自己的p连边，流量为inf

p2相T连边，流量为理科same的高兴值，相邻点和自己的p向p2连边，流量为inf

然后跑一下网络流就好了

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 3e4 + 10;

const int M = 1e6 + 5;

const int inf = 1e8;

const int dx[5] = {0, 1, -1, 0, 0};

const int dy[5] = {0, 0, 0, 1, -1};

struct edge {

    int next, to, f;

    edge() {}

    edge(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {}

} e[M];

int n, m, S, T, ans;

int w[105][105], cnt_p;

int first[N], tot = 1;

int q[N], d[N];

inline int read() {

    int x = 0;

    char ch = getchar();

    while (ch < '0' || '9' < ch)

        ch = getchar();

    while ('0' <= ch && ch <= '9') {

        x = x * 10 + ch - '0';

        ch = getchar();

    }

    return x;

}

inline void Add_Edges(int x, int y, int f) {

    e[++tot] = edge(first[x], y, f), first[x] = tot;

    e[++tot] = edge(first[y], x, 0), first[y] = tot;

}

#define y e[x].to

#define p q[l]

bool bfs() {

  int l, r, x;

  memset(d, -1, sizeof(d));

  d[q[1] = S] = 1;

  for (l = r = 1; l != r + 1; ++l)

    for (x = first[p]; x; x = e[x].next)

      if (!~d[y] && e[x].f) {

    d[q[++r] = y] = d[p] + 1;

    if (y == T) return 1;

      }

  return 0;

}

#undef p

int dfs(int p, int lim) {

  if (p == T || !lim) return lim;

  int x, tmp, rest = lim;

  for (x = first[p]; x && rest; x = e[x].next)

    if (d[y] == d[p] + 1 && ((tmp = min(e[x].f, rest)) > 0)) {

      rest -= (tmp = dfs(y, tmp));

      e[x].f -= tmp, e[x ^ 1].f += tmp;

      if (!rest) return lim;

    }

  if (rest) d[p] = -1;

  return lim - rest;

}

#undef y

inline int Dinic() {

  int res = 0;

  while (bfs())

    res += dfs(S, inf);

  return res;

}

inline bool in(int x, int y) {

    return x && y && x <= n && y <= m;

}

#define X i + dx[k]

#define Y j + dy[k]

#define p1(i, j) w[i][j] * 3

#define p2(i, j) w[i][j] * 3 + 1

#define p3(i, j) w[i][j] * 3 + 2

int main() {

    int i, j, k, x;

    n = read(), m = read();

    for (i = 1; i <= n; ++i)

        for (j = 1; j <= m; ++j)

            w[i][j] = ++cnt_p;

    S = n * m * 3 + 3, T = S + 1;

    for (i = 1; i <= n; ++i)

        for (j = 1; j <= m; ++j)

            Add_Edges(S, p1(i, j), x = read()), ans += x;

    for (i = 1; i <= n; ++i)

        for (j = 1; j <= m; ++j)

            Add_Edges(p1(i, j), T, x = read()), ans += x;

    for (i = 1; i <= n; ++i)

        for (j = 1; j <= m; ++j) {

            Add_Edges(S, p2(i, j), x = read()), ans += x;

            for (k = 0; k <= 4; ++k)

                if (in(X, Y)) Add_Edges(p2(i, j), p1(X, Y), inf);

        }

    for (i = 1; i <= n; ++i)

        for (j = 1; j <= m; ++j) {

            Add_Edges(p3(i, j), T, x = read()), ans += x;

            for (k = 0; k <= 4; ++k)

                if (in(X, Y)) Add_Edges(p1(X, Y), p3(i, j), inf);

        }

    printf("%d\n", ans - Dinic());

    return 0;

}

巴特西