BZOJ 1412 & 最小割-白红宇

BZOJ 1412 & 最小割

阅读量：5150 次

发布时间：2019-06-13

本文共 2902 字，大约阅读时间需要 9 分钟。

什么时候ZJ省选再现一次这么良心的题吧...

题意:

　　在一个染色的格子画分割线,使其不想连,求最少的线段

SOL:

　　裸裸的最小割.题目要求两种颜色不想连,我们把他分到两个集合,也就是把所有相连的边切断-----这不就是最小割嘛. 把其中一个颜色与源相连,另一个颜色与汇相连,容量为正无穷,然后中间相连的容量均为1,然后跑下dinic即可.

Code:

/*==========================================================================# Last modified: 2016-03-11 18:09# Filename: 1412.cpp# Description: ==========================================================================*/#define me AcrossTheSky #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
               #include 
               
                 #include 
                
                  #include 
                 
                   #define lowbit(x) (x)&(-x) #define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++) #define FORP(i,a,b) for(int i=(a);i<=(b);i++) #define FORM(i,a,b) for(int i=(a);i>=(b);i--) #define ls(a,b) (((a)+(b)) << 1) #define rs(a,b) (((a)+(b)) >> 1) #define getlc(a) ch[(a)][0] #define getrc(a) ch[(a)][1] #define maxn 10005 #define maxm 100000 #define pi 3.1415926535898 #define _e 2.718281828459 #define inf 1070000000 using namespace std; typedef long long ll; typedef unsigned long long ull; template
                  
                    inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*==================split line==================*/ using namespace std;int first[maxn],d[maxn],cur[maxn];bool vis[maxn];int cnt=1,n,m;int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},mp[105][105];struct data{int to,next,v;}e[500001];int T,S;void ins(int u,int v,int w){e[++cnt].to=v;e[cnt].next=first[u];e[cnt].v=w;first[u]=cnt;}void insert(int u,int v,int w){ins(u,v,w);ins(v,u,0);}int bfs(){ queue
                   
                     q; for(int i=S;i<=T;i++) vis[i]=false; q.push(0); d[0]=0; vis[0]=true; while (!q.empty()){ int now=q.front(); q.pop(); for (int i=first[now];i;i=e[i].next) if (!vis[e[i].to] && e[i].v){ d[e[i].to]=d[now]+1; vis[e[i].to]=true; q.push(e[i].to); } } return vis[T];}int dfs(int now,int a){ if (now==T || !a) return a; int f,flow=0; for (int & i=cur[now];i;i=e[i].next) if (d[now]+1==d[e[i].to] && (f=dfs(e[i].to,min(a,e[i].v)))>0){ flow+=f; a-=f; e[i].v-=f; e[i^1].v+=f; if (!a) break; } return flow; }int dinic(){ int ans=0; while(bfs()){ FORP(i,0,T) cur[i]=first[i]; ans+=dfs(0,inf); } return ans;}void init(){ read(n); read(m); T=n*m+1,S=0; FORP(i,1,n) FORP(j,1,m) read(mp[i][j]);}void build(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(mp[i][j]==1)insert(0,(i-1)*m+j,inf); else if(mp[i][j]==2)insert((i-1)*m+j,T,inf); for(int k=0;k<4;k++) { int nowx=i+xx[k],nowy=j+yy[k]; if(nowx<1||nowx>n||nowy<1||nowy>m||mp[i][j]==2)continue; if(mp[i][j]!=1||mp[nowx][nowy]!=1) insert((i-1)*m+j,(nowx-1)*m+nowy,1); } } }int main(){ init(); build(); printf("%d",dinic()); return 0;}

转载于:https://www.cnblogs.com/YCuangWhen/p/5266781.html

你可能感兴趣的文章