这道题一定要写一下，卡了好久。
题意：
有黑白两种方格，最上边一行和最左边一列一定是黑色，然后其余的地方有可能是黑色，有可能是白色，和白色相邻的黑色方格里有数字(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 = 100 + 5; const int maxm = 1e6 + 5; 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[10]; 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 = 0; ed[tot].next = head[v]; head[v] = tot; } inline void init(){ memset( head, -1 ,sizeof(head) ); tot = 1; } inline void map_set(){ for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ ){ int cnt = 0; if( mp[i][j].type==4 ){ for( int k=j+1; k<m && mp[i][k].type==1; k++ ) add( num[i][k], num[i][j], 8 ), cnt ++; add( num[i][j], tp, mp[i][j].top-cnt ); }else if( mp[i][j].type==2 ){ for( int k=j+1; k<m && mp[i][k].type==1; k++ ) add( num[i][k], num[i][j], 8 ), cnt ++; add( num[i][j], tp, mp[i][j].top-cnt ); cnt = 0; for( int k=i+1; k<n && mp[k][j].type==1; k++ ) add( num[i][j]-1, num[k][j], 8 ), cnt ++; //type==2时，让num[i][j]-1代表左下数字的点 add( sp, num[i][j]-1, mp[i][j].lft-cnt ); }else if( mp[i][j].type==3 ){ for( int k=i+1; k<n && mp[k][j].type==1; k++ ) add( num[i][j], num[k][j], 8 ), cnt ++; add( sp, num[i][j], mp[i][j].lft-cnt ); } } } inline bool bfs(){ memset( d, 0, sizeof(d) ); queue<int> q; d[sp] = 1; q.push(sp); while( !q.empty() ){ int x = q.front(); q.pop(); for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w && !d[y] ){ d[y] = d[x] + 1; q.push(y); if( y==tp ) return 1; } } } return 0; } 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!=-1 && rest; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w && d[y]==d[x]+1 ){ k = dfs( y, min(rest, ed[i].w) ); if(!k) d[y] = 0; ed[i].w -= k; ed[i^1].w += k; rest -= k; } } return flow - rest; } inline void dinic(){ int flow = maxflow = 0; while( bfs() ){ while( flow=dfs(sp, inf) ) maxflow += flow; //该题里 maxflow没什么用，可以不求 } } inline void output(){ memset( ans, 0, sizeof(ans) ); //ans记录答案 for( int i=head[sp]; i!=-1; i=ed[i].next ){ //超级源点sp是虚拟的，正好利用它进行遍历 int u = ed[i].to; for( int j=head[u]; j!=-1; j=ed[j].next ) ans[ed[j].to] = 8 - ed[j].w + 1; //最后要加回1(其实这里为什么要减去边权而不直接用边权我不是很懂，求dalao指教) } for( int i=0; i<n; i++ ){ putchar('_'); for( int j=1; j<m; j++ ){ if( mp[i][j].type!=1 ) 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 = 0; for( int i=0; i<n; i++ ) for( int j=0; j<m; j++ ){ scanf("%s", s); if( s[0]=='.' ){ mp[i][j].type = 1; mp[i][j].top = mp[i][j].lft = 0; }else if( s[0]=='X' ){ if( s[4]=='X' ) mp[i][j].type = 0; else{ mp[i][j].type = 4; mp[i][j].lft = 0; mp[i][j].top = (s[4]-'0')*100 + (s[5]-'0')*10 + s[6]-'0'; } }else{ if( s[4]=='X' ){ mp[i][j].type = 3; mp[i][j].lft = (s[0]-'0')*100 + (s[1]-'0')*10 + s[2]-'0'; mp[i][j].top = 0; }else{ mp[i][j].type = 2; mp[i][j].lft = (s[0]-'0')*100 + (s[1]-'0')*10 + s[2]-'0'; mp[i][j].top = (s[4]-'0')*100 + (s[5]-'0')*10 + s[6]-'0'; } } if( mp[i][j].type==2 ) nump += 2; //type == 2的时候就是上半部分和左半部分都有数字，那么将其拆点成两个点 else nump ++; num[i][j] = nump; //将矩阵的二维编码转换成一维，便于进行操作 } sp = 0; tp = nump+1; map_set(); dinic(); output(); } return 0; }