【BZOJ3894】文理分科

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

Solution

试机的时候写的。。。贾教流。

对于一个集合选or不选产生的代价/价值可以通过新建附加点来解决。

Code

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #define R register

 #define filename ""

 #define maxn 100010

 #define maxm 600010

 #define inf 0x7fffffff

 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

 struct Edge {

     Edge *next, *rev;

     int to, cap;

 } *cur[maxn], *last[maxn], e[maxm], *ecnt = e;

 inline void link(R int a, R int b, R int w)

 {

     *++ecnt = (Edge) {last[a], ecnt + , b, w}; last[a] = ecnt;

     *++ecnt = (Edge) {last[b], ecnt - , a, }; last[b] = ecnt;

 }

 const int dx[] = {, -, , }, dy[] = {, , , -};

 int id[][], s, t, ans, q[maxn], dep[maxn], tot;

 inline bool bfs()

 {

     R int head = , tail = ;

     memset(dep, -, (tot + ) << );

     dep[q[] = t] = ;

     while (head < tail)

     {

         R int now = q[++head];

         for (R Edge *iter = last[now]; iter; iter = iter -> next)

             if (iter -> rev -> cap && dep[iter -> to] == -)

                 dep[q[++tail] = iter -> to] = dep[now] + ;

     }

     return dep[s] != -;

 }

 int dfs(R int x, R int f)

 {

     if (x == t) return f;

     R int used = ;

     for (R Edge* &iter = cur[x]; iter; iter = iter -> next)

         if (iter -> cap && dep[iter -> to] +  == dep[x])

         {

             R int v = dfs(iter -> to, dmin(iter -> cap, f - used));

             iter -> cap -= v;

             iter -> rev -> cap += v;

             used += v;

             if (used == f) return f;

         }

     return used;

 }

 inline void dinic()

 {

     while (bfs())

     {

         memcpy(cur, last, (tot + ) << );

         ans += dfs(s, inf);

     }

 }

 int main()

 {

 //    freopen(filename".in", "r", stdin);

 //    freopen(filename".out", "w", stdout);

     R int n, m; scanf("%d%d", &n, &m);

     R int anss = ;

     for (R int i = ; i <= n; ++i)

         for (R int j = ; j <= m; ++j)

         {

             id[i][j] = ++tot; R int art;

             scanf("%d", &art); link(s, tot, art); anss += art;

         }

     t = ++tot;

     for (R int i = ; i <= n; ++i)

         for (R int j = ; j <= m; ++j)

         {

             R int sc; scanf("%d", &sc); anss += sc;

             link(id[i][j], t, sc);

         }

     for (R int i = ; i <= n; ++i)

         for (R int j = ; j <= m; ++j)

         {

             R int as; scanf("%d", &as); ++tot; anss += as;

             for (R int k = ; k < ; ++k)

             {

                 R int nx = i + dx[k], ny = j + dy[k];

                 if (id[nx][ny]) link(tot, id[nx][ny], inf);

             }

             link(tot, id[i][j], inf);

             link(s, tot, as);

         }

     for (R int i = ; i <= n; ++i)

         for (R int j = ; j <= m; ++j)

         {

             R int ss; scanf("%d", &ss); ++tot; anss += ss;

             for (R int k = ; k < ; ++k)

             {

                 R int nx = i + dx[k], ny = j + dy[k];

                 if (id[nx][ny]) link(id[nx][ny], tot, inf);

             }

             link(id[i][j], tot, inf);

             link(tot, t, ss);

         }

     dinic();

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

     return ;

 }

巴特西

【BZOJ3894】文理分科

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

Code

最新文章

热门文章

巴特西

【BZOJ3894】 文理分科

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

Code

最新文章

热门文章

【BZOJ3894】文理分科