首页 > 代码库 > hdoj 3338 Kakuro Extension 【经典最大流+输出流量】
hdoj 3338 Kakuro Extension 【经典最大流+输出流量】
题目:hdoj 3338 Kakuro Extension
定义:神级最大流(各种错误无数次,整整一天)
题意:一个游戏,这个游戏给出一个矩阵,有些矩阵里面有两个数,前面一个数表示从下一行到下一个出现数字行的所有数字和(当前这一列),而第二个数表示从下一列到下一个出现数字的列(当前这一行),让你填入满足条件的数字的矩阵(1---9),可以重复(最大流条件)。
分析:首先数字可以重复那么确定了可以用最大流来做,建图方法就是列进行出,或者行进列出,前者比较好写。
这个题目还有一个条件就是要求必须有流量,因为最低是1,这样的话我们可以写给初始的和减去值的数量,然后在最后求出之后+1,加回来就可以。
经典的在于建图方法。下面说一下。
首先预处理,对图中的每个格子编不同编号cnt,然后处理处所有行和编号为raw_cnt,所有列和编号col_cnt。
那么设置一个超级源点s,建边 s 到所有行和raw_cnt,容量为行和。
然后行和raw_cnt建边连到当前这个和是由哪几个数字的和得到的,连接起编号cnt,容量为8.
然后同样列和col_cnt 建边由当前列那几个 cnt 组成,每个建边,容量为8.
然后列和col_cnt 连接 超级汇点 t ,容量为列和。
然后就是输出每一个流过去的流量就ok。
这个题目同样C++比G++快大约300ms。所以网络流还是C++提交比较好,
AC代码:
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> using namespace std; #define Del(a,b) memset(a,b,sizeof(a)) const int N = 20500; const int inf = 0x3f3f3f3f; int n,m; struct Node { int from,to,cap,flow; }; vector<int> v[N]; vector<Node> e; int vis[N]; //构建层次图 int cur[N]; void add_Node(int from,int to,int cap) { e.push_back((Node){from,to,cap,0}); e.push_back((Node){to,from,0,0}); int tmp=e.size(); v[from].push_back(tmp-2); v[to].push_back(tmp-1); } bool bfs(int s,int t) { Del(vis,-1); queue<int> q; q.push(s); vis[s] = 0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<v[x].size();i++) { Node tmp = e[v[x][i]]; if(vis[tmp.to]<0 && tmp.cap>tmp.flow) //第二个条件保证 { vis[tmp.to]=vis[x]+1; q.push(tmp.to); } } } if(vis[t]>0) return true; return false; } int dfs(int o,int f,int t) { if(o==t || f==0) //优化 return f; int a = 0,ans=0; for(int &i=cur[o];i<v[o].size();i++) //注意前面 ’&‘,很重要的优化 { Node &tmp = e[v[o][i]]; if(vis[tmp.to]==(vis[o]+1) && (a = dfs(tmp.to,min(f,tmp.cap-tmp.flow),t))>0) { tmp.flow+=a; e[v[o][i]^1].flow-=a; //存图方式 ans+=a; f-=a; if(f==0) //注意优化 break; } } return ans; //优化 } int dinci(int s,int t) { int ans=0; while(bfs(s,t)) { Del(cur,0); int tm=dfs(s,inf,t); ans+=tm; } return ans; } int mp[250][250]; struct Node1 { int x,y,z; }; Node1 raw[N],col[N]; int solve(int raw_cnt,int id,int s) { int cnt = 0,pos = id+raw_cnt; return e[v[pos][1]].flow+1; } int main() { //freopen("Input.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { memset(mp,-1,sizeof(mp)); memset(col,0,sizeof(col)); memset(raw,0,sizeof(raw)); int cnt=0,raw_cnt=0,col_cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { string str; cin>>str; if(str[0] == '.'){ mp[i][j] = ++cnt; }else{ mp[i][j] = -1; if(str[0] != 'X'){ int tmp = (str[0]-'0')*100 + (str[1]-'0')*10 + str[2]-'0'; col[++col_cnt].x = i; col[col_cnt].y = j; col[col_cnt].z = tmp; } if(str[4] != 'X'){ int tmp = (str[4]-'0')*100 + (str[5]-'0')*10 + str[6]-'0'; raw[++raw_cnt].x = i; raw[raw_cnt].y = j; raw[raw_cnt].z = tmp; } } } } //printf("%d %d %d\n",raw_cnt,col_cnt,cnt); int start=0,t=col_cnt+cnt+raw_cnt+2; for(int i = 1;i <= raw_cnt;i++){ int x = raw[i].x; int y = raw[i].y; int cnt_len = 0; for(y = y+1;y <= m;y++){ if(mp[x][y] != -1){ cnt_len++; add_Node(i,raw_cnt+mp[x][y],8); } else break; } add_Node(start,i,raw[i].z-cnt_len); } for(int i = 1;i <= col_cnt;i++){ int x = col[i].x; int y = col[i].y; int cnt_len = 0; for(x = x+1;x <= n;x++){ if(mp[x][y] != -1){ cnt_len++; add_Node(raw_cnt+mp[x][y],raw_cnt+cnt+i,8); } else break; } add_Node(raw_cnt+cnt+i,t,col[i].z-cnt_len); } int ans=dinci(start,t); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mp[i][j]==-1) printf("_"); else printf("%d",solve(raw_cnt,mp[i][j],cnt)); printf("%c",j==m?'\n':' '); } } for(int i=0;i<=t;i++) v[i].clear(); e.clear(); } return 0; }
hdoj 3338 Kakuro Extension 【经典最大流+输出流量】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。