Advertisement
STEFAN_STOYANOV

2785_Himiya za 70

May 19th, 2022
562
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<string>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<deque>
  10. #include<cstdio>
  11. #include<fstream>
  12. #include<map>
  13. #include<set>
  14. using namespace std;
  15. const int maxe=(1<<14),maxel=64,maxn=(1<<12),inf=(1<<30);
  16. struct edge
  17. {
  18.     int to,cap,next;
  19.     edge(){}
  20.     edge(int _to,int _cap,int _next)
  21.     {
  22.         to=_to;
  23.         cap=_cap;
  24.         next=_next;
  25.     }
  26. };
  27. edge e[maxe];int bre;
  28. int sum_of_a;
  29. int n,m,allv,a[maxel][maxel],S,T,F,p;
  30. int head[maxn],ptr[maxn],path[maxn],sz=0;
  31. int lvl[maxn];
  32. void read()
  33. {
  34.     cin>>n>>m;
  35.     string s;
  36.     for(int i=1;i<=n;i++)
  37.     {
  38.         cin>>s;
  39.         for(int j=0;j<m;++j)
  40.         {
  41.             switch(s[j])
  42.             {
  43.                 case 'H':a[i][j+1]=1;
  44.                          sum_of_a+=a[i][j+1];
  45.                          break;
  46.                 case 'O':a[i][j+1]=2;
  47.                          sum_of_a+=a[i][j+1];
  48.                          break;
  49.                 case 'N':a[i][j+1]=3;
  50.                          sum_of_a+=a[i][j+1];
  51.                          break;
  52.                 case 'C':a[i][j+1]=4;
  53.                          sum_of_a+=a[i][j+1];
  54.                          break;
  55.             }
  56.         }
  57.     }
  58. }
  59. void add_edge(int from,int to,int cap)
  60. {
  61.     e[bre]=edge(to,cap,head[from]);
  62.     head[from]=bre;bre++;
  63. }
  64. void init_graph()
  65. {
  66.     memset(head,-1,sizeof(head));
  67.     S=0;T=n*m+1;
  68.     int cur,cur1;
  69.     for(int i=1;i<=n;++i)
  70.         for(int j=1;j<=m;++j)
  71.         {
  72.             if(a[i][j])
  73.             {
  74.                 cur=(i-1)*m+j;
  75.                 if((i%2==1&&j%2==1)||(i%2==0&&cur%2==0))
  76.                 {
  77.                     add_edge(S,cur,a[i][j]);
  78.                     add_edge(cur,S,0);
  79.                     if(1<i)
  80.                     {
  81.                         if(a[i-1][j])
  82.                         {
  83.                             cur1=(i-2)*m+j;
  84.                             add_edge(cur,cur1,1);
  85.                             add_edge(cur1,cur,0);
  86.                         }
  87.                     }
  88.                     if(i<n)
  89.                     {
  90.                         if(a[i+1][j])
  91.                         {
  92.                             cur1=(i)*m+j;
  93.                             add_edge(cur,cur1,1);
  94.                             add_edge(cur1,cur,0);
  95.                         }
  96.                     }
  97.                     if(1<j)
  98.                     {
  99.                         if(a[i][j-1])
  100.                         {
  101.                             cur1=(i-1)*m+j-1;
  102.                             add_edge(cur,cur1,1);
  103.                             add_edge(cur1,cur,0);
  104.                         }
  105.                     }
  106.                     if(j<m)
  107.                     {
  108.                         if(a[i][j+1])
  109.                         {
  110.                             cur1=(i-1)*m+j+1;
  111.                             add_edge(cur,cur1,1);
  112.                             add_edge(cur1,cur,0);
  113.                         }
  114.                     }
  115.                 }
  116.                 else
  117.                 {
  118.                     add_edge(cur,T,a[i][j]);
  119.                     add_edge(T,cur,0);
  120.                 }
  121.             }
  122.         }
  123. }
  124. bool BFS()
  125. {
  126.     memset(lvl,0,sizeof(lvl));
  127.     lvl[T]=1;
  128.     queue<int>q;
  129.     q.push(T);
  130.     int w;
  131.     while(!q.empty())
  132.     {
  133.         w=q.front();
  134.         q.pop();
  135.         for(int i=head[w];i!=-1;i=e[i].next)
  136.             if(lvl[e[i].to]==0&&e[i^1].cap>0)
  137.         {
  138.             lvl[e[i].to]=lvl[w]+1;
  139.             q.push(e[i].to);
  140.         }
  141.     }
  142.     return lvl[S];
  143. }
  144. bool DFS(int ver)
  145. {
  146.     if(ver==T)return 1;
  147.     for(int i=ptr[ver];i!=-1;i=ptr[ver]=e[i].next)
  148.         if(lvl[e[i].to]+1==lvl[ver]&&e[i].cap>0)
  149.         {
  150.             if(DFS(e[i].to))
  151.             {
  152.                 if(p>e[i].cap)
  153.                     p=e[i].cap;
  154.                 path[sz]=i;
  155.                 sz++;
  156.                 return 1;
  157.             }
  158.         }
  159.     return 0;
  160. }
  161. void inline update()
  162. {
  163.     int x;
  164.     for(int i=0;i<sz;++i)
  165.     {
  166.         x=path[i];
  167.         e[x].cap-=p;
  168.         e[x^1].cap-=p;
  169.     }
  170. }
  171. void Dinitz()
  172. {
  173.     while(BFS())
  174.     {
  175.         for(int i=0;i<=n*m+1;++i)
  176.             ptr[i]=head[i];
  177.         sz=0;
  178.         p=inf;
  179.         while(DFS(S))
  180.         {
  181.             F+=p;
  182.             update();
  183.             sz=0;
  184.             p=inf;
  185.         }
  186.     }
  187.     if(F*2==sum_of_a)
  188.         cout<<"Valid\n";
  189.     else cout<<"Invalid\n";
  190. }
  191. int main()
  192. {
  193.     ios_base::sync_with_stdio(false);
  194.     cin.tie(NULL);
  195.     cout.tie(NULL);
  196.     read();
  197.     init_graph();
  198.     /*cout<<"Initializated graph\n";
  199.     for(int i=0;i<=n*m+1;i++)
  200.     {
  201.         cout<<"i=="<<i<<endl;
  202.         for(int j=head[i];j!=-1;j=e[j].next)
  203.             cout<<e[j].to<<' '<<e[j].cap<<endl;
  204.         cout<<endl;
  205.     }
  206.     cout<<endl;*/
  207.     Dinitz();
  208. return 0;
  209. }
  210. /*
  211. 3 4
  212. HOH.
  213. NCOH
  214. OO..
  215. */
  216.  
Advertisement
RAW Paste Data Copied
Advertisement