Description
地圖是個矩形的網格。
可以花費一定金錢在一些格子投資。
被投資的格子或者四連通的格子都被投資的話，我就可以獲得該格子的收益。
利益最大化是作為商人的基本準則，但這是計算機的任務，拜托您了。
Input
第一行兩個數 n,m(n,m ≤ 20)，表示矩形的長和寬。
接下來 n 行，每行是 m 個字元組成的字元串，描述投資的花費。
接下來 n 行，每行是 m 個字元組成的字元串，表示該格子的收益。
花費和收益按照一種奇葩的方式給出：
字元 數
‘0’ -’ 9’ 0-9
‘a’ -’ z’ 10-35
‘A’ -’ Z’ 36-61
Output
一個數，表示收益的和減去投資的和的最大值。
Sample Input
【樣例 1】
2 2
21
12
21
12
【樣例 2】
2 2
ZZ
ZZ
11
11
【樣例 3】
3 3
XXX
XXX
XXX
aaa
aZa
aaa
【樣例 4】
2 4
asam
atik
123A
45BC
【樣例 5】
9 8
IIIIIIII
IIWWWWII
IIWIIIII
IIWIIIII
IIWWWWII
IIIIIWII
IIIIIWII
IIWWWWII
IIIIIIII
IIIIIIII
II0000II
II0II0II
II0II0II
II0000II
II0II0II
II0II0II
II0000II
IIIIIIII
Data Constraint
n,m ≤ 20.
分析：
一看到這一題，好像文理分科啊，然後按着這個想法推了一下。
首先一塊地可以選和不選，選了要花錢，不選就拿不到這塊地的價值。是以我們考慮把所有價值加起來，然後用最小割解決。
建圖模型，大概是這樣的，沒寫權值的邊為 INF I N F
首先一個拆成三個點，然後第一個點向第二個點連一條 costi c o s t i 的邊，第二個點向第三個點連一條 valuei v a l u e i 的邊，這兩條邊要斷掉一個，即選或不選。如果切掉 costi c o s t i 的邊，則說明我們買了該點，要減去買的費用；否則為不買，因為我們一開始 ans a n s 是所有價值的和，是以要減去。
還有一種方法可以得到這個權值，那就是把周圍的點全部買下來，周圍的點記為 j j ，即把costjcostj全部割掉，也就是上圖左邊的三條邊；如果有一個 j j 割的是valuejvaluej的邊，就是有一個不買，都要割掉 valuei v a l u e i 的邊。肯定不可能 valuej v a l u e j 和 costj c o s t j 同時割掉，這樣就血虧了，而且也不可能。
然後我們給這個棋盤黑白染色，黑點在一邊，白點在一邊，然後跑最大流就可以了。
好像拆成兩個點也可以，不過資料範圍很小。
一開始想法是把 costi c o s t i 放一邊， valuei v a l u e i 放另外一邊，怎麼想都做不出來= =
代碼：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
const int inf=;
using namespace std;
int n,m,cnt,s,t,ans;
int cost[][],value[][];
int dis[],ls[];
queue <int> q;
struct edge{
int y,c,op,next;
}g[];
int calc(char ch)
{
if ((ch>='0') && (ch<='9')) return (ch-'0');
if ((ch>='a') && (ch<='z')) return (ch-'a'+);
return (ch-'A'+);
}
void init()
{
char s[],ch;
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
{
scanf("%s",s);
scanf("%c",ch);
for (int j=;j<=m;j++)
{
cost[i][j]=calc(s[j-]);
}
}
for (int i=;i<=n;i++)
{
scanf("%s",s);
scanf("%c",ch);
for (int j=;j<=m;j++)
{
value[i][j]=calc(s[j-]);
ans+=value[i][j];
}
}
}
void add(int x,int y,int w)
{
g[++cnt]=(edge){y,w,cnt+,ls[x]};
ls[x]=cnt;
g[++cnt]=(edge){x,,cnt-,ls[y]};
ls[y]=cnt;
}
int op(int x,int y)
{
return (x-)*m+y-;
}
bool bfs()
{
for (int i=s;i<=t;i++) dis[i]=;
dis[s]=;
while (!q.empty()) q.pop();
q.push(s);
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i=ls[u];i>;i=g[i].next)
{
int v=g[i].y;
if ((dis[v]==) && (g[i].c))
{
dis[v]=dis[u]+;
if (v==t) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int x,int maxf)
{
if ((x==t) || (maxf==)) return maxf;
int ret=;
for (int i=ls[x];i>;i=g[i].next)
{
int y=g[i].y;
if ((dis[x]+==dis[y]) && (g[i].c))
{
int f=dfs(y,min(maxf-ret,g[i].c));
g[i].c-=f;
g[g[i].op].c+=f;
ret+=f;
}
}
return ret;
}
int main()
{
init();
s=; t=n*m*3+;
for (int i=;i<=n;i++)
{
for (int j=;j<=m;j++)
{
if ((i+j)%2==)
{
int x=op(i,j);
add(s,x*3+,inf);
add(x*3+,x*3+,cost[i][j]);
add(x*3+,x*3+,value[i][j]);
if (i>)
{
int y=op(i-,j);
add(x*3+,y*3+,inf);
add(x*3+,y*3+,inf);
}
if (i<n)
{
int y=op(i+,j);
add(x*3+,y*3+,inf);
add(x*3+,y*3+,inf);
}
if (j>)
{
int y=op(i,j-);
add(x*3+,y*3+,inf);
add(x*3+,y*3+,inf);
}
if (j<m)
{
int y=op(i,j+);
add(x*3+,y*3+,inf);
add(x*3+,y*3+,inf);
}
}
else
{
int x=op(i,j);
add(x*3+,t,inf);
add(x*3+,x*3+,cost[i][j]);
add(x*3+,x*3+,value[i][j]);
}
}
}
while (bfs()) ans-=dfs(s,inf);
printf("%d",ans);
}