fzu2143 Board Game

Board Game

Accept: 54 Submit: 151
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of the board which is own by Fat brother is consisting of an integer 0. At each turn, he can choose two adjacent grids and add both the integer inside them by 1. But due to some unknown reason, the number of each grid can not be large than a given integer K. Also, Maze has already drown an N*M board with N*M integers inside each grid. What Fat brother would like to do is adding his board to be as same as Maze’s. Now we define the different value of two boards A and B as:

Now your task is to help Fat brother the minimal value of S he can get.

Input

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each case contains three integers N, M and K which are mention above. Then N lines with M integers describe the board.

1 <= T <= 100, 1 <= N, M, K <= 9

0 <= the integers in the given board <= 9

Output

For each case, output the case number first, then output the minimal value of S Fat brother can get.

Sample Input

2 2 9

3 4

2 3

1 3 9

4 6 4

1 1 9

3 3 5

1 2 3

4 5 6

7 8 9

3 3 9

1 2 3

4 5 6

7 8 9

Sample Output

Case 1: 0

Case 2: 2

Case 3: 81

Case 4: 33

Case 5: 5

解题：转自http://blog.csdn.net/henryascend/article/details/38663589

建图什么的太不懂了

最小费用流

每次操作只更改相邻的两个数，可看作棋盘模型，黑白两色

对于a[i,j] ，对答案的贡献为

a[i,j]^2 - 2*a[i,j]*b[i,j] + b[i,j]^2

b[i,j]^2 为常项 , 对于a[i,j] ，由选p-1到p时，答案增加了 2p - 1 - 2*b

对于所有白色点，添加源点至白点的K条边，花费为 2p-1-2*b, 流量为1，

对于所有黑色点，添加黑点至汇点的K条边，花费为 2p-1-2*b, 流量为1，

任意相邻的黑白点之间添加花费为0，流量无穷的一条边，

在图上跑最小费用流，当d[T]>=0时，对答案已无影响，即可退出

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<queue>
  5 using namespace std;
  6 struct Edge {
  7     int from, to , cap, flow, cost , next;
  8 };
  9 const int inf = 0x3f3f3f3f;
 10 int n,m,K;
 11 Edge edge[3010];
 12 int head[110];
 13 int dx[4]= {0,0,-1,1};
 14 int dy[4]= {-1,1,0,0};
 15 int map[11][11];
 16 int d[110],a[110],p[110];
 17 bool vis[110];
 18 int ans,cnt;
 19 void add(int from, int to , int cap, int cost) {
 20     edge[cnt].from = from;
 21     edge[cnt].to = to;
 22     edge[cnt].cap =cap;
 23     edge[cnt].flow = 0;
 24     edge[cnt].cost = cost;
 25     edge[cnt].next = head[from];
 26     head[from] = cnt ++;
 27 
 28     edge[cnt].from = to;
 29     edge[cnt].to = from;
 30     edge[cnt].cap = 0;
 31     edge[cnt].flow = 0;
 32     edge[cnt].cost = -cost;
 33     edge[cnt].next = head[to];
 34     head[to] = cnt ++;
 35 }
 36 
 37 bool bound(int x,int y) {
 38     return ( x>=1 && x<=n && y>=1 && y<=m );
 39 }
 40 
 41 bool spfa(int S, int T, int &flow, int &cost) {
 42     memset(d,63,sizeof(d));
 43     memset(vis, 0, sizeof(vis));
 44     queue <int> q;
 45     d[S] = 0;
 46     a[S] = inf;
 47     vis[S] = 1;
 48     p[S] = 0;
 49     q.push(S);
 50     while (!q.empty()) {
 51         int u = q.front();
 52         q.pop();
 53         int i=head[u];
 54         while (i!=-1) {
 55             int v= edge[i].to;
 56             if (edge[i].cap>edge[i].flow && d[v]>d[u]+edge[i].cost) {
 57                 d[v] = d[u] +edge[i].cost;
 58                 p[v] = i;
 59                 a[v] = min( a[u], edge[i].cap - edge[i].flow);
 60                 if (!vis[v]) {
 61                     q.push(v);
 62                     vis[v] =1;
 63                 }
 64             }
 65             i = edge[i].next;
 66         }
 67         vis[u]=0;
 68     }
 69     if (d[T]>=0)  return false;
 70     flow += a[T];
 71     cost += d[T] * a[T];
 72     int u= T;
 73     while ( u!=S ) {
 74         edge[ p[u] ] .flow +=a[T];
 75         edge[ p[u]^1 ].flow -=a[T];
 76         u=edge[ p[u] ].from;
 77     }
 78     return true;
 79 }
 80 
 81 void Mincost (int S, int T) {
 82     int flow = 0 , cost = 0;
 83     while ( spfa(S, T, flow, cost) );
 84     ans += cost;
 85 }
 86 int main() {
 87     int T,cas=0;
 88     scanf("%d",&T);
 89     while (T--) {
 90         memset(head,-1,sizeof(head));
 91         cnt =ans = 0;
 92         scanf("%d%d%d",&n,&m,&K);
 93         int idx=0, x;
 94         int st= 0,  en = n*m+1;
 95         for (int i=1; i<=n; i++)
 96             for (int j=1; j<=m; j++) {
 97                 scanf("%d",&x);
 98                 ans += x * x;
 99                 map[i][j]= ++idx;
100                 for (int k=1; k<=K; k++)
101                     if ( i % 2 == j % 2)
102                         add( st, map[i][j], 1 , 2*k -1 - 2*x );
103                     else
104                         add( map[i][j],en , 1 , 2*k -1 - 2*x );
105             }
106         for (int i=1; i<=n; i++)
107             for (int j=1; j<=m; j++) {
108                 if ( i % 2 == j % 2 )
109                     for (int k=0; k<4; k++) {
110                         int tx=  i + dx[k];
111                         int ty=  j + dy[k];
112                         if (!bound( tx,ty))  continue;
113                         add(map[i][j], map[tx][ty],inf, 0);
114                     }
115             }
116         Mincost(st, en);
117         printf("Case %d: %d
",++cas,ans);
118     }
119     return 0;
120 }

View Code