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

題意：

有黑白兩種方格，最上邊一行和最左邊一列一定是黑色，然后其余的地方有可能是黑色，有可能是白色，和白色相鄰的黑色方格里有數(shù)字(1個(gè)或2個(gè))，

現(xiàn)在要求在白色方格里填1~9中的一個(gè)數(shù)字，使得一個(gè)黑色方格下邊的數(shù)字 = sigma(該黑色方格下邊白色方格數(shù)字)? 這個(gè)sigma不是下邊全部的白方格，

而是一直往下走一直走到一個(gè)黑方格之前所有的白方格，詳情見(jiàn)樣例1。相同的，黑方格右上角的數(shù)字 = sigma(該黑色方格右邊白色方格數(shù)字)。

思路：

可以很容易看出，所有白色方格按行相加 == 所有白色方格按列相加? 也就是? 所有黑色方格右上角數(shù)字和 == 所有黑色方格左下角數(shù)字和。那么符合網(wǎng)絡(luò)流，

源點(diǎn)輸入的流量==匯點(diǎn)匯入的流量。建立超級(jí)源點(diǎn)sp和超級(jí)匯點(diǎn)tp，然后進(jìn)行以下設(shè)定：

?

type = 0，不帶數(shù)字的黑色方格

type = 1，白色方格

type = 2，帶有兩個(gè)數(shù)字的黑色方格(這個(gè)要進(jìn)行拆點(diǎn)，代碼里會(huì)標(biāo)記)

type = 3，只有左下角帶數(shù)字的黑色方格

type = 4，只有右上角帶數(shù)字的黑色方格

把黑色方格左下角作為源點(diǎn)，白色方格作為中間點(diǎn)，黑色方格右上角作為匯點(diǎn)。(也可以源點(diǎn)匯點(diǎn)交換一下，如下一行的括號(hào))

接下來(lái)進(jìn)行連邊 sp -> type2.3 -> type1 -> type2.4 -> tp。(也可以sp -> type2.4 -> type1 -> type2.3 -> tp)

因?yàn)榘追礁褚?~9有下界1和上界9兩個(gè)界線，不如讓填的數(shù)減一，最后再加上，就變成了填0~8可以方便的進(jìn)行最大流操作

sp -> type2.3連邊時(shí)，邊權(quán)為左下角的數(shù)減去下邊白色方格數(shù)*1（因?yàn)槎紲p1了）

type2.4 -> tp連邊時(shí)，邊權(quán)為右上角的數(shù)減去右邊白色方格數(shù)*1

type2.3 -> type1 -> type2.4連邊時(shí)，邊權(quán)設(shè)為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時(shí)，讓num[i][j]-1代表左下數(shù)字的點(diǎn)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沒(méi)什么用，可以不求 } }inline void output(){memset( ans, 0, sizeof(ans) ); //ans記錄答案for( int i=head[sp]; i!=-1; i=ed[i].next ){ //超級(jí)源點(diǎn)sp是虛擬的，正好利用它進(jìn)行遍歷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(其實(shí)這里為什么要減去邊權(quán)而不直接用邊權(quán)我不是很懂，求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的時(shí)候就是上半部分和左半部分都有數(shù)字，那么將其拆點(diǎn)成兩個(gè)點(diǎn)else nump ++;num[i][j] = nump; //將矩陣的二維編碼轉(zhuǎn)換成一維，便于進(jìn)行操作 }sp = 0; tp = nump+1;map_set();dinic();output();}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/WAautomaton/p/10992351.html

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。