这道题一定要写一下，卡了好久。
题意：
有黑白两种方格，最上边一行和最左边一列一定是黑色，然后其余的地方有可能是黑色，有可能是白色，和白色相邻的黑色方格里有数字(1个或2个)，
现在要求在白色方格里填1~9中的一个数字，使得一个黑色方格下边的数字 = sigma(该黑色方格下边白色方格数字) 这个sigma不是下边全部的白方格，
而是一直往下走一直走到一个黑方格之前所有的白方格，详情见样例1。相同的，黑方格右上角的数字 = sigma(该黑色方格右边白色方格数字)。
思路：
可以很容易看出，所有白色方格按行相加 == 所有白色方格按列相加 也就是 所有黑色方格右上角数字和 == 所有黑色方格左下角数字和。那么符合网络流，
源点输入的流量==汇点汇入的流量。建立超级源点sp和超级汇点tp，然后进行以下设定：
type = 0，不带数字的黑色方格
type = 1，白色方格
type = 2，带有两个数字的黑色方格(这个要进行拆点，代码里会标记)
type = 3，只有左下角带数字的黑色方格
type = 4，只有右上角带数字的黑色方格
把黑色方格左下角作为源点，白色方格作为中间点，黑色方格右上角作为汇点。(也可以源点汇点交换一下，如下一行的括号)
接下来进行连边 sp -> type2.3 -> type1 -> type2.4 -> tp。(也可以sp -> type2.4 -> type1 -> type2.3 -> tp)
因为白方格要填1~9有下界1和上界9两个界线，不如让填的数减一，最后再加上，就变成了填0~8可以方便的进行最大流操作
sp -> type2.3连边时，边权为左下角的数减去下边白色方格数*1（因为都减1了）
type2.4 -> tp连边时，边权为右上角的数减去右边白色方格数*1
type2.3 -> type1 -> type2.4连边时，边权设为8
然后跑最大流，求答案
#include <bits/stdc++.h>
using namespace std; const int maxn = + ;
const int maxm = 1e6 + ;
const int inf = 0x3f3f3f3f;
int n, m, d[maxn*maxn], sp, tp, maxflow;
int head[maxn*maxn], tot;
struct point{
int top, lft, type;
} mp[maxn][maxn];
struct edge{
int to, w, next;
} ed[maxm];
int num[maxn][maxn], ans[maxn*maxn];
char s[];
inline void add( int u, int v, int w ){
ed[++tot].to = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot;
ed[++tot].to = u; ed[tot].w = ; ed[tot].next = head[v]; head[v] = tot;
} inline void init(){
memset( head, - ,sizeof(head) );
tot = ;
} inline void map_set(){
for( int i=; i<n; i++ )
for( int j=; j<m; j++ ){
int cnt = ;
if( mp[i][j].type== ){
for( int k=j+; k<m && mp[i][k].type==; k++ )
add( num[i][k], num[i][j], ), cnt ++;
add( num[i][j], tp, mp[i][j].top-cnt );
}else if( mp[i][j].type== ){
for( int k=j+; k<m && mp[i][k].type==; k++ )
add( num[i][k], num[i][j], ), cnt ++;
add( num[i][j], tp, mp[i][j].top-cnt );
cnt = ;
for( int k=i+; k<n && mp[k][j].type==; k++ )
add( num[i][j]-, num[k][j], ), cnt ++; //type==2时，让num[i][j]-1代表左下数字的点
add( sp, num[i][j]-, mp[i][j].lft-cnt );
}else if( mp[i][j].type== ){
for( int k=i+; k<n && mp[k][j].type==; k++ )
add( num[i][j], num[k][j], ), cnt ++;
add( sp, num[i][j], mp[i][j].lft-cnt );
}
}
} inline bool bfs(){
memset( d, , sizeof(d) );
queue<int> q;
d[sp] = ;
q.push(sp);
while( !q.empty() ){
int x = q.front();
q.pop();
for( int i=head[x]; i!=-; i=ed[i].next ){
int y = ed[i].to;
if( ed[i].w && !d[y] ){
d[y] = d[x] + ;
q.push(y);
if( y==tp ) return ;
}
}
}
return ;
} inline int min( int a, int b ){
return a<b ? a:b;
} inline int dfs( int x, int flow ){
if( x==tp ) return flow;
int rest = flow, k;
for( int i=head[x]; i!=- && rest; i=ed[i].next ){
int y = ed[i].to;
if( ed[i].w && d[y]==d[x]+ ){
k = dfs( y, min(rest, ed[i].w) );
if(!k) d[y] = ;
ed[i].w -= k;
ed[i^].w += k;
rest -= k;
}
}
return flow - rest;
} inline void dinic(){
int flow = maxflow = ;
while( bfs() ){
while( flow=dfs(sp, inf) ) maxflow += flow; //该题里 maxflow没什么用，可以不求
}
} inline void output(){
memset( ans, , sizeof(ans) ); //ans记录答案
for( int i=head[sp]; i!=-; i=ed[i].next ){ //超级源点sp是虚拟的，正好利用它进行遍历
int u = ed[i].to;
for( int j=head[u]; j!=-; j=ed[j].next )
ans[ed[j].to] = - ed[j].w + ; //最后要加回1(其实这里为什么要减去边权而不直接用边权我不是很懂，求dalao指教)
}
for( int i=; i<n; i++ ){
putchar('_');
for( int j=; j<m; j++ ){
if( mp[i][j].type!= ) printf(" _");
else printf("%2d", ans[num[i][j]]);
}
puts("");
}
} int main(){
// freopen("in.txt", "r", stdin);
while( ~scanf("%d%d", &n, &m) ){
init();
int nump = ;
for( int i=; i<n; i++ )
for( int j=; j<m; j++ ){
scanf("%s", s);
if( s[]=='.' ){
mp[i][j].type = ;
mp[i][j].top = mp[i][j].lft = ;
}else if( s[]=='X' ){
if( s[]=='X' ) mp[i][j].type = ;
else{
mp[i][j].type = ;
mp[i][j].lft = ;
mp[i][j].top = (s[]-'')* + (s[]-'')* + s[]-'';
}
}else{
if( s[]=='X' ){
mp[i][j].type = ;
mp[i][j].lft = (s[]-'')* + (s[]-'')* + s[]-'';
mp[i][j].top = ;
}else{
mp[i][j].type = ;
mp[i][j].lft = (s[]-'')* + (s[]-'')* + s[]-'';
mp[i][j].top = (s[]-'')* + (s[]-'')* + s[]-'';
}
}
if( mp[i][j].type== ) nump += ; //type == 2的时候就是上半部分和左半部分都有数字，那么将其拆点成两个点
else nump ++;
num[i][j] = nump; //将矩阵的二维编码转换成一维，便于进行操作
}
sp = ; tp = nump+;
map_set();
dinic();
output();
} return ;
}