題目鏈接：點(diǎn)擊查看

題目大意：填數(shù)游戲，給出一個(gè)n*m的矩陣，矩陣中存在三種方塊：

純黑的方塊：沒什么用

純白的方塊：等待我們填數(shù)字的方塊

黑色方塊上有數(shù)字：

左下角有數(shù)字：當(dāng)前黑色方塊下面的白色方塊內(nèi)數(shù)字之和等于當(dāng)前數(shù)字

右上角有數(shù)字：當(dāng)前黑色方塊右面的白色方塊內(nèi)數(shù)字之和等于當(dāng)前數(shù)字

在滿足上述規(guī)則的條件下，將矩陣補(bǔ)充完整

題目分析：因?yàn)樵谔顚懢仃嚨臅r(shí)候，可以使用重復(fù)數(shù)字，數(shù)字的范圍是1~9，所以題目相對(duì)來說還是比較簡單的，稍微分析一下可以知道，對(duì)于每個(gè)白色方塊，影響其內(nèi)部數(shù)字的因素?zé)o非就是其最左邊的黑色方塊與其最上面的黑色方塊，所以如果用網(wǎng)絡(luò)流的話，我們將其互相建邊就好了，因?yàn)榘咨綁K和左邊的黑色方塊與上邊的黑色方塊有關(guān)系，換句話說，其鏈接了左邊與上邊的黑色方塊，不妨從源點(diǎn)流出一股流量，經(jīng)過向下的黑色方塊后途徑白色方塊再經(jīng)過向右的黑色方塊最后流向匯點(diǎn)，這樣跑完最大流后，因?yàn)榍捌谠诮ㄟ厱r(shí)對(duì)于各個(gè)地方流量的限制，我們就可以控制最大流在規(guī)定范圍內(nèi)了，最后跑一邊殘余網(wǎng)絡(luò)就能找到答案了

有幾個(gè)需要注意的細(xì)節(jié)，首先是數(shù)字的范圍是1~9，而每條邊的流量是可以達(dá)到0的，為了方便處理，我們可以將數(shù)值映射到流量后整體減少1，將其規(guī)定為0~8對(duì)應(yīng)著1~9，最后對(duì)參與網(wǎng)絡(luò)操作的時(shí)候記得加一就好了，然后就是這個(gè)題的數(shù)據(jù)稍微有點(diǎn)大，用dinic會(huì)被卡常，所以可以選擇用SAP來跑最大流，其他的沒什么注意的了，直接說一下具體的建邊方法吧：

源點(diǎn)->所有向下的黑色方塊，流量為其數(shù)字減去與其有關(guān)系的白色方塊個(gè)數(shù)之差(因?yàn)?~9變成了0~8，所以整體減去了1)

所有向下的黑色方塊->與其有關(guān)系的白色方塊，流量為8

所有白色方塊->與其有關(guān)系的向右的黑色方塊，流量為8

所有向右的黑色方塊->匯點(diǎn)，流量為其數(shù)字減去與其有關(guān)系的白色方塊的個(gè)數(shù)之差(原理同上)

這樣跑完最大流后直接對(duì)殘余網(wǎng)絡(luò)操作就好了，因?yàn)樗械暮谏綁K最后都是需要輸出下劃線的，所以對(duì)于每個(gè)白色方塊，我們找一下與其有關(guān)系的向右的黑色方塊的連邊，用邊權(quán)的殘余流量就可以計(jì)算出跑最大流使用了多少流量了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e4+100;//點(diǎn)數(shù)的最大值const int M=2e5+100;//邊數(shù)的最大值struct Node {int from,to,next;int cap; }edge[M];int tol,head[N],dep[N],gap[N];//gap[x]=y :說明殘留網(wǎng)絡(luò)中dep[i]==x的個(gè)數(shù)為yint nn;//n是總的點(diǎn)的個(gè)數(shù)，包括源點(diǎn)和匯點(diǎn)int n,m;struct Maze {char s[8]; }maze[110][110];int mark[110][110];//記錄每個(gè)白點(diǎn)對(duì)應(yīng)的向右的黑格 int ans[110][110];void init() {tol=0;nn=2;memset(head,-1,sizeof(head));memset(ans,-1,sizeof(ans)); }void addedge(int u,int v,int w) {edge[tol].from=u;edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++;edge[tol].from=v;edge[tol].to=u;edge[tol].cap=0;edge[tol].next=head[v];head[v]=tol++; } void BFS(int start,int end) {memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0]=1;int que[N];int front,rear;front=rear=0;dep[end]=0;que[rear++]=end;while(front!=rear){int u=que[front++];if(front==N)front=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(dep[v]!=-1)continue;que[rear++]=v;if(rear==N)rear=0;dep[v]=dep[u]+1;++gap[dep[v]];}} } int SAP(int start,int end) {int res=0;BFS(start,end);int cur[N];int S[N];int top=0;memcpy(cur,head,sizeof(head));int u=start;int i;while(dep[start]<nn){if(u==end){int temp=inf;int inser;for(i=0;i<top;i++)if(temp>edge[S[i]].cap){temp=edge[S[i]].cap;inser=i;}for(i=0;i<top;i++){edge[S[i]].cap-=temp;edge[S[i]^1].cap+=temp;}res+=temp;top=inser;u=edge[S[top]].from;}if(u!=end&&gap[dep[u]-1]==0)//出現(xiàn)斷層，無增廣路break;for(i=cur[u];i!=-1;i=edge[i].next)if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)break;if(i!=-1){cur[u]=i;S[top++]=i;u=edge[i].to;}else{int min=nn;for(i=head[u];i!=-1;i=edge[i].next){if(edge[i].cap==0)continue;if(min>dep[edge[i].to]){min=dep[edge[i].to];cur[u]=i;}}--gap[dep[u]];dep[u]=min+1;++gap[dep[u]];if(u!=start)u=edge[S[--top]].from;}}return res; }int get_id(int x,int y,int k)//k=0:向下 k=1:向右 k=2:空白格 {return (x-1)*m+y+k*n*m; }bool check(int x,int y)//判斷(x,y)是否為空白格 {if(x<=0||y<=0||x>n||y>m)return false;return maze[x][y].s[0]=='.'; }int get_num(char s[],int st)//得到點(diǎn)(x,y)的數(shù)字，st代表著起始位置，0代表第一個(gè)數(shù)，4代表第二個(gè)數(shù) {int ans=0;for(int i=st;i<st+3;i++)ans=ans*10+s[i]-'0';return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%s",&maze[i][j].s);int st=N-1,ed=st-1;//源點(diǎn)->向下的黑點(diǎn)->空白格->向右的黑點(diǎn)->匯點(diǎn) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(check(i,j)){nn++;continue;}if(maze[i][j].s[0]!='X')//向下 {nn++;int sum=0;int xx=i+1,yy=j;while(check(xx,yy)){addedge(get_id(i,j,0),get_id(xx,yy,2),8);//向下的黑格->空白格 sum++;xx++;}addedge(st,get_id(i,j,0),get_num(maze[i][j].s,0)-sum);//源點(diǎn)->向下的黑格 }if(maze[i][j].s[4]!='X')//向右 {nn++;int sum=0;int xx=i,yy=j+1;while(check(xx,yy)){mark[xx][yy]=get_id(i,j,1);addedge(get_id(xx,yy,2),get_id(i,j,1),8);//空白格->向右的黑格 sum++;yy++; }addedge(get_id(i,j,1),ed,get_num(maze[i][j].s,4)-sum);//向右的黑格->匯點(diǎn) }}}SAP(st,ed);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(maze[i][j].s[0]=='.'){int u=get_id(i,j,2);for(int k=head[u];k!=-1;k=edge[k].next){if(edge[k].to==mark[i][j])//找到了之前建的邊，根據(jù)殘余流量計(jì)算答案{ans[i][j]=9-edge[k].cap;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(ans[i][j]==-1)printf("_ ");elseprintf("%d ",ans[i][j]);}printf("\n");}} return 0; }

?

總結(jié)

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

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