這道題一定要寫一下，卡了好久。

題意：

有黑白兩種方格，最上邊一行和最左邊一列一定是黑色，然后其余的地方有可能是黑色，有可能是白色，和白色相鄰的黑色方格里有數字(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; }

?

轉載于:https://www.cnblogs.com/WAautomaton/p/10992351.html

總結

以上是生活随笔為你收集整理的HDU3338 Kakuro Extension(最大流+思维构图)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。