Advertisement
STEFAN_STOYANOV

2785_2nd try

May 23rd, 2022
648
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<cstring>
  3. #include<queue>
  4. using namespace std;
  5. const int maxe=(1<<14),maxel=64,maxn=(1<<12);
  6. struct edge
  7. {
  8.     int to,cap,next;
  9.     edge(){}
  10.     edge(int _to,int _cap,int _next)
  11.     {
  12.         to=_to;
  13.         cap=_cap;
  14.         next=_next;
  15.     }
  16. };
  17. edge e[maxe];int bre;
  18. int n,m,head[maxn],ptr[maxn],S,T,F;
  19. int lvl[maxn],path[maxe],sz;
  20. int a[maxel][maxel],Sum_of_a;
  21. void read()
  22. {
  23.     cin>>n>>m;
  24.     string s;
  25.     for(int i=1;i<=n;++i)
  26.     {
  27.         cin>>s;
  28.         for(int j=0;j<m;++j)
  29.         {
  30.             switch(s[j])
  31.             {
  32.                 case 'H':a[i][j+1]=1;
  33.                          break;
  34.                 case 'O':a[i][j+1]=2;
  35.                          break;
  36.                 case 'N':a[i][j+1]=3;
  37.                          break;
  38.                 case 'C':a[i][j+1]=3;
  39.                          break;
  40.             }
  41.             Sum_of_a+=a[i][j+1];
  42.         }
  43.     }
  44. }
  45. void add_edge(int from,int to,int cap)
  46. {
  47.     edge[bre]=edge(to,cap,head[from]);
  48.     head[from]=bre;bre++;
  49. }
  50. void init_graph()
  51. {
  52.     memset(head,-1,sizeof(head));
  53.     S=0;
  54.     T=n*m+1;
  55.     int cur,to;
  56.     for(int i=1;i<=n;++i)
  57.         for(int j=1;j<=m;++j)
  58.         {
  59.             cur=(i-1)*m+j;
  60.             if(i%2==j%2)
  61.             {
  62.                 add_edge(S,cur,a[i][j]);
  63.                 add_edge(cur,S,0);
  64.                 if(1<i)
  65.                 {
  66.                     to=(i-2)*m+j;
  67.                     add_edge(cur,to,1);
  68.                     add_edge(to,cur,0);
  69.                 }
  70.                 if(i<n)
  71.                 {
  72.                     to=i*m+j;
  73.                     add_edge(cur,to,1);
  74.                     add_edge(to,cur,0);
  75.                 }
  76.                 if(1<j)
  77.                 {
  78.                     to=(i-1)*m+j-1;
  79.                     add_edge(cur,to,1);
  80.                     add_edge(to,cur,0);
  81.                 }
  82.                 if(j<m)
  83.                 {
  84.                     to=(i-1)*m+j+1;
  85.                     add_edge(cur,to,1);
  86.                     add_edge(to,cur,0);
  87.                 }
  88.             }
  89.             else
  90.             {
  91.                 add_edge(cur,T,a[i][j]);
  92.                 add_edge(T,cur,0);
  93.             }
  94.         }
  95. }
  96. bool BFS()
  97. {
  98.     memset(lvl,0,sizeof(lvl));
  99.     lvl[T]=1;
  100.     queue<int>q;
  101.     q.push(T);
  102.     int w,i;
  103.     while(!q.empty())
  104.     {
  105.         w=q.front();
  106.         q.pop();
  107.         for(i=head[w];i!=-1;i=e[i].next)
  108.             if(!lvl[e[i].to]&&e[i^1].cap>0)
  109.             {
  110.                 q.push(e[i].to);
  111.                 lvl[e[i].to]=lvl[w]+1;
  112.             }
  113.     }
  114.     return lvl[S];
  115. }
  116. void Dinitz()
  117. {
  118.  
  119. }
  120. int main()
  121. {
  122.  
  123. return 0;
  124. }
  125.  
Advertisement
RAW Paste Data Copied
Advertisement