首页 > 代码库 > Topcoder--SRM570Div1--1000--CurvyonRails
Topcoder--SRM570Div1--1000--CurvyonRails
巨强的一道题
对于可行解的判定,考虑对于每个城市都会有两个铁路断点,而每个铁路断点必须和另一个铁路断点结合,而棋盘图又是天然二分图,所以第一阶段考虑判断可行解的建图方式为: 棋盘黑白染色,源点向所有白点连边,所有黑点向汇点连边,容量均为2.然后所有白点向相邻黑点连容量为1点边,如果跑出最大流使源汇均满流则原图有解。
至此容易观察到如果可行,黑白点数量必然相同,且流量为黑点数*2。
之后为了解决题目中的第二个问题,我们考虑如果能将问题转化到费用流上面就会很清真。
怎么转化为费用流呢?
因为曲线有4种情况而直线只有2种,所以考虑计算直线费用。
首先可以看出如果走的是直线,那么对于一个方格内的铁路必然均链接横向或均链接纵向,那么我们把所有有小动物的点拆出两个点,分别代表匹配橫行和匹配纵行,然后对于两个可匹配度都匹配相同方向的就可以轻松统计了。
具体建图看代码吧
代码(无费用流部分):
int p[30][30],n,m,fix,fix2,mk[30][30],sz; int wt,bl; int getmin(vector<string> field) { S=MAXN-2;T=MAXN-3;cnt=1; n=field.size();m=field[0].size(); fix=n*m;fix2=fix<<1; for(int i=0;i<n;i++) for(int j=0;j<m;j++) p[i+1][j+1]=field[i][j]==‘.‘?1:(field[i][j]==‘C‘?2:0); for(int t,i=1;i<=n;i++) for(int j=1;j<=m;j++) { mk[i][j]=++sz; if(!p[i][j]) continue; t=(i+j)&1; if(t) { insert(S,mk[i][j],2,0,1);wt++; } else { insert(mk[i][j],T,2,0,1);bl++; } if(p[i][j]==1) { insert(mk[i][j],mk[i][j]+fix,2,0,t); insert(mk[i][j],mk[i][j]+fix2,2,0,t); } else { insert(mk[i][j],mk[i][j]+fix,1,0,t); insert(mk[i][j],mk[i][j]+fix,1,1,t); insert(mk[i][j],mk[i][j]+fix2,1,0,t); insert(mk[i][j],mk[i][j]+fix2,1,1,t); } } for(int t,i=1;i<=n;i++) for(int j=1;j<=m;j++) { t=(i+j)&1;if(!t) continue; if(p[i-1][j]) insert(mk[i][j]+fix,mk[i-1][j]+fix,1,0,1); if(p[i+1][j]) insert(mk[i][j]+fix,mk[i+1][j]+fix,1,0,1); if(p[i][j-1]) insert(mk[i][j]+fix2,mk[i][j-1]+fix2,1,0,1); if(p[i][j+1]) insert(mk[i][j]+fix2,mk[i][j+1]+fix2,1,0,1); } MSMF(); if(bl!=wt||flow!=bl*2) return -1; return cost; }
Topcoder--SRM570Div1--1000--CurvyonRails
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。