Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- #include<string>
- #include<vector>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<cstdio>
- #include<fstream>
- #include<map>
- #include<set>
- using namespace std;
- const int maxa=32,inf=(1<<30),maxe=1e7+10,maxn=2048;
- struct edge
- {
- int to,next,cap;
- edge(){}
- edge(int _to,int _next,int _cap)
- {
- to=_to;
- next=_next;
- cap=_cap;
- }
- };
- edge e[maxe];int bre;
- int n,m,allv,a[maxa][maxa],S,T,F,p;
- int lvl[maxn],head[maxn],ptr[maxn],path[maxe],sz;
- void read()
- {
- cin>>n;
- string s;
- for(int i=1;i<=n;++i)
- {
- cin>>s;
- m=s.size();
- for(int j=0;j<m;++j)
- a[i][j+1]=(int)s[j]-(int)'0';
- }
- }
- void inline add_edge(int from,int to,int cap)
- {
- e[bre]=edge(to,head[from],cap);
- head[from]=bre;bre++;
- }
- void init_graph()
- {
- memset(head,-1,sizeof(head));
- allv=n*m;
- S=0;T=allv+1;
- int cur;
- ///end rows
- for(int i=1;i<=m;++i)
- {
- ///goren red
- cur=i;
- add_edge(cur,cur+allv+1,1);
- add_edge(cur+allv+1,cur,1);
- add_edge(cur+allv+1,T,1);
- add_edge(T,cur+allv+1,0);
- if(a[1][i])
- {
- add_edge(S,cur,1);
- add_edge(cur,S,0);
- }
- ///dolen red
- cur=(n-1)*m+i;
- add_edge(cur,cur+allv+1,1);
- add_edge(cur+allv+1,cur,1);
- add_edge(cur+allv+1,T,1);
- add_edge(T,cur+allv+1,0);
- if(a[n][i])
- {
- add_edge(S,cur,1);
- add_edge(cur,S,0);
- }
- }
- for(int i=1;i<m;++i)
- {
- ///goren red
- cur=i;
- add_edge(cur+allv+1,cur+1,1);add_edge(cur+1,cur+allv+1,0);
- add_edge(cur+1+allv+1,cur,1);add_edge(cur,cur+1+allv+1,0);
- ///dolen red
- cur=(n-1)*m+i;
- add_edge(cur+allv+1,cur+1,1);add_edge(cur+1,cur+allv+1,0);
- add_edge(cur+1+allv+1,cur,1);add_edge(cur,cur+1+allv+1,0);
- }
- ///end colums
- for(int i=2;i<n;++i)
- {
- ///lqva kolona
- cur=(i-1)*m+1;
- add_edge(cur,cur+allv+1,1);
- add_edge(cur+allv+1,cur,1);
- add_edge(cur+allv+1,T,1);
- add_edge(T,cur+allv+1,0);
- if(a[i][1])
- {
- add_edge(S,cur,1);
- add_edge(cur,S,0);
- }
- ///dqsna kolona
- cur=(i-1)*m+m;
- add_edge(cur,cur+allv+1,1);
- add_edge(cur+allv+1,cur,1);
- add_edge(cur+allv+1,T,1);
- add_edge(T,cur+allv+1,0);
- if(a[i][1])
- {
- add_edge(S,cur,1);
- add_edge(cur,S,0);
- }
- }
- for(int i=1;i<n;++i)
- {
- ///lqva kolona
- cur=(i-1)*m+1;
- add_edge(cur+allv+1,cur+m,1);add_edge(cur+m,cur+allv+1,0);
- add_edge(cur+m+allv+1,cur,1);add_edge(cur,cur+m+allv+1,0);
- ///dqsna kolona
- cur=(i-1)*m+m;
- add_edge(cur+allv+1,cur+m,1);add_edge(cur+m,cur+allv+1,0);
- add_edge(cur+m+allv+1,cur,1);add_edge(cur,cur+m+allv+1,0);
- }
- ///central
- for(int i=2;i<n;++i)
- {
- for(int j=2;j<m;++j)
- {
- cur=(i-1)*m+j;
- add_edge(cur,cur+allv+1,1);
- add_edge(cur+allv+1,cur,1);
- if(a[i][j])
- {
- add_edge(S,cur,1);
- add_edge(cur,S,0);
- }
- add_edge(cur+allv+1,cur-m,1);add_edge(cur-m,cur+allv+1,0);
- add_edge(cur-m+allv+1,cur,1);add_edge(cur,cur-m+allv+1,0);
- add_edge(cur+allv+1,cur-1,1);add_edge(cur-1,cur+allv+1,0);
- add_edge(cur-1+allv+1,cur,1);add_edge(cur,cur-1+allv+1,0);
- }
- }
- for(int i=2;i<m;++i)
- {
- cur=(n-1)*m+i;
- ///nqma nuzhda ot dublirane i checkvane za iztochnik
- add_edge(cur+allv+1,cur-m,1);add_edge(cur-m,cur+allv+1,0);
- add_edge(cur-m+allv+1,cur,1);add_edge(cur,cur-m+allv+1,0);
- }
- for(int i=2;i<n;++i)
- {
- cur=(i-1)*m+m;
- ///nqma nuzhda ot dublirane i checkvane za iztochnik
- add_edge(cur+allv+1,cur-1,1);add_edge(cur-1,cur+allv+1,0);
- add_edge(cur-1+allv+1,cur,1);add_edge(cur,cur-1+allv+1,0);
- }
- }
- bool BFS()
- {
- //cout<<"In BFS\n";
- memset(lvl,0,sizeof(lvl));
- lvl[T]=1;
- queue<int>q;
- q.push(T);
- int w,nb,i;
- while(!q.empty())
- {
- w=q.front();
- q.pop();
- //cout<<"In while BFS\n";
- for(i=head[w]/*,cout<<"in for BFS\n"*/;i!=-1;i=e[i].next)
- if(!lvl[e[i].to]&&e[i^1].cap>0)
- {
- //cout<<"in if for BFS\n";
- lvl[e[i].to]=lvl[w]+1;
- //cout<<lvl[e[i].to]<<' '<<e[i].to<<' '<<w<<endl;
- q.push(e[i].to);
- }
- }
- //cout<<"Exit BFS\n";
- return lvl[S];
- }
- bool DFS(int ver)
- {
- if(ver==T)return true;
- for(int i=ptr[ver];i!=-1;i=ptr[ver]=e[i].next)
- {
- if(lvl[e[i].to]+1==lvl[ver]&&e[i].cap>0)
- {
- if(DFS(e[i].to))
- {
- if(e[i].cap<p)p=e[i].cap;
- path[sz]=i;
- sz++;
- return true;
- }
- }
- }
- return false;
- }
- void update()
- {
- int x;
- for(int i=0;i<sz;++i)
- {
- x=path[i];
- e[x].cap-=p;
- e[x^1].cap+=p;
- }
- }
- void Dinitz()
- {
- while(BFS())
- {
- /*for(int i=1;i<=2*n*m+1;i++)
- cout<<lvl[i]<<' ';*/
- cout<<"Passed BFS\n";
- for(int i=0;i<=2*n*m+1;i++)
- ptr[i]=head[i];
- sz=0;
- p=inf;
- while(DFS(S))
- {
- F+=p;
- cout<<p<<' '<<F<<endl;
- update();
- p=inf;
- sz=0;
- }
- //cout<<endl;
- }
- cout<<F<<endl;
- }
- int main()
- {
- /*ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);*/
- read();
- /*cout<<endl;
- for(int i=1;i<=n;++i,cout<<endl)
- for(int j=1;j<=m;++j)
- cout<<a[i][j]<<' ';*/
- init_graph();
- cout<<"Initializated graph\n";
- for(int i=0;i<=2*n*m+1;i++)
- {
- cout<<"i=="<<i<<endl;
- for(int j=head[i];j!=-1;j=e[j].next)
- cout<<e[j].to<<' '<<e[j].cap<<endl;
- cout<<endl;
- }
- cout<<endl;
- Dinitz();
- return 0;
- }
- /*
- 3
- 0001
- 0110
- 1001
- */
- /*
- 3
- 110
- 010
- 001
- */
- /*
- 5
- 111010
- 000101
- 111101
- 111001
- 001000
- */
Add Comment
Please, Sign In to add comment