首页 > 代码库 > 【不可能的任务12/200】bzoj1412最小割
【不可能的任务12/200】bzoj1412最小割
太羞耻了,m n写反了(主要是样例n m相等)
建图方法比较高(ji)端(chu),对于可以加栅栏的地方连上1的边,然后求最小割即可
为了让代码优(suo)美(duan),我写了一个check,避免多次重复的时候犯错(简直是我这种mn都能打反的人必备)
1 #include <cstdio> 2 #define INF 2147483647 3 int n,m,N=1,h,t,zl,ans; 4 int a[101][101],fir[10100],d[10100],to[100000],flo[100000],nex[100000],l[10100]; 5 inline void add(int x,int y,int z){ to[++N]=y;flo[N]=z;nex[N]=fir[x];fir[x]=N; 6 to[++N]=x;flo[N]=0;nex[N]=fir[y];fir[y]=N;} 7 inline int min(int x,int y){ return(x<y)?x:y;} 8 inline void check(int x,int y,int X,int Y) 9 {10 if(X==0 || Y==0 || X>n || Y>m) return;11 if(a[x][y]!=2 && a[X][Y]!=1) add((x-1)*m+y,(X-1)*m+Y,1); 12 }13 bool bfs()14 {15 for(int i=1;i<=n*m+1;i++) d[i]=0;16 for(h=1,t=1,l[1]=0,d[0]=1;h<=t;h++)17 for(int i=fir[l[h]];i;i=nex[i])18 if(!d[to[i]] && flo[i])19 l[++t]=to[i],d[l[t]]=d[l[h]]+1;20 return d[n*m+1];21 }22 int dfs(int now,int flow,int sum)23 {24 if(now==n*m+1) return flow;25 for(int i=fir[now];i && (sum<flow);i=nex[i])26 if(d[to[i]]==d[now]+1 && flo[i])27 zl=dfs(to[i],min(flow-sum,flo[i]),0),sum+=zl,flo[i]-=zl,flo[i^1]+=zl;28 if(sum==0) d[now]=0;29 return sum;30 }31 int main()32 {33 scanf("%d%d",&n,&m);34 for(int i=1;i<=n;i++)35 for(int j=1;j<=m;j++)36 {37 scanf("%d",&a[i][j]);38 if(a[i][j]==1) add(0,(i-1)*m+j,INF);39 if(a[i][j]==2) add((i-1)*m+j,n*m+1,INF);40 }41 for(int i=1;i<=n;i++)42 for(int j=1;j<=m;j++)43 check(i,j,i-1,j),check(i,j,i+1,j),check(i,j,i,j-1),check(i,j,i,j+1);44 for(ans=0;bfs();ans+=dfs(0,INF,0));45 printf("%d\n",ans);46 return 0;47 }
让我好好想想最近在犯什么错:
1.%d多打或少打
2.输入顺序没看清
3.行数和列数没分清
人生无望。。。我还是滚回普及组去吧
【不可能的任务12/200】bzoj1412最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。