P2172 [国家集训队]部落战争【最小路径覆盖】

题目背景

lanzerb 的部落在 A 国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。

题目描述

A 国是一个 $M\times NM×N 的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb 把自己的部落分成若干支军队，他们约定：$

每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。

如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。每支军队都可以在任意一个城镇停止征战。

所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走 $1\times21×2 的路线，而他们只能走 R\times CR×C 的路线。$

lanzerb 的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮 lanzerb 算算至少要多少支军队才能完成统一全国的大业。

输入格式

第一行包含

输出格式

输出一个整数，表示最少的军队个数。

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

3 3 1 2
...
.x.
...

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

输入 #2<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

5 4 1 1
....
..x.
...x
....
x...

输出 #2<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

思路

　　说是国集但貌似很好想是一个最小路径覆盖问题。

　　可能本意是考搜索吗？

　　针对补充下上一篇题解忘记说的一个问题（写的时候太困了

　　最小路径覆盖问题的建图是和普通网络流建图有区别的

　　为了保证路径数最小，就必须尽量将两条路线首尾相连

　　所以每个点的入点是要连能够接触到的点的出点的。

　　针对此题来说，能触碰到的点无非是走马的四种情形。

　　x点对建图的影响仅是不能将x点作为起点罢了

　　∵ 最小路径覆盖 = 点数 - 最大独立集

　　∴只要求出最大独立集的大小即可

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 2e4 + 7;
 49 
 50 int s, t, cnt;
 51 char a[100][100];
 52 int head[maxn << 1], edge[maxn << 1], nxt[maxn << 1], vis[maxn << 1];
 53 int w[maxn << 1];//残量网络
 54 int rev[maxn << 1];
 55 int depth[maxn << 1];//图层
 56 int n, m;
 57 
 58 inline int id(int a, int b) {
 59     return (a - 1) * n + b;
 60 }
 61 
 62 inline void BuildGraph(int u, int v, int cap) {
 63     ++cnt;
 64     edge[cnt] = v;
 65     nxt[cnt] = head[u];
 66     rev[cnt] = cnt + 1;
 67     w[cnt] = cap;
 68     head[u] = cnt;
 69 
 70     ++cnt;
 71     edge[cnt] = u;
 72     nxt[cnt] = head[v];
 73     w[cnt] = 0;
 74     rev[cnt] = cnt - 1;
 75     head[v] = cnt;
 76 }
 77 
 78 bool bfs(int x) {
 79     queue<int> q;
 80     while(!q.empty()) {
 81         q.pop();
 82     }
 83     memset(depth, 63, sizeof(depth));
 84     depth[s] = 0;
 85     q.push(s);
 86     do {
 87         int u = q.front();
 88         q.pop();
 89         for ( int i = head[u]; i; i = nxt[i] ) {
 90             int v = edge[i];
 91             if(w[i] > 0 && depth[u] + 1 < depth[v]) {
 92                 depth[v] = depth[u] + 1;
 93                 q.push(v);
 94                 if(v == t) {
 95                     return true;
 96                 }
 97             }
 98         }
 99     } while (!q.empty());
100     return false;
101 }
102 
103 int dfs(int u, int dist) {
104     if(u == t) {
105         return dist;
106     }
107     for ( int i = head[u]; i; i = nxt[i] ) {
108         int v = edge[i];
109         if(depth[v] == depth[u] + 1 && w[i] > 0) {
110             int di = dfs(v, min(dist, w[i]));
111             if(di > 0) {
112                 w[i] -= di;
113                 w[rev[i]] += di;
114                 //vis[u] = v;
115                 //printf("vis[%d]:%d\n",u, v);
116                 return di;
117             }
118         }
119     }
120     return 0;
121 }
122 
123 bool check(int x, int y) {
124     if(x >= 1 && x <= m && y >= 1 && y <= n) {
125         return true;
126     }
127     return false;
128 }
129 
130 int main()
131 {
132     //freopen("data.txt", "r", stdin);
133     int r, c;
134     memset(vis, 0, sizeof(vis));
135     read(m); read(n); read(r); read(c);
136     s = 0, t = 2 * n * m + 1;
137     for ( int i = 1; i <= m; ++i ) {
138         for ( int j = 1; j <= n; ++j ) {
139             cin >> a[i][j];
140         }
141     }
142     int cnt = 0;
143     for ( int i = 1; i <= m; ++i ) {
144         for ( int j = 1; j <= n; ++j ) {
145             if(a[i][j] == '.') {
146                 BuildGraph(s, id(i, j), 1);
147                 BuildGraph(id(i, j) + n * m, t, 1);
148                 int nxt_x = i + r, nxt_y = j + c;
149                 if(check(nxt_x, nxt_y)) {
150                     BuildGraph(id(i, j), id(nxt_x, nxt_y) + n * m, 1);
151                 }
152                 nxt_x = i + r, nxt_y = j - c;
153                 if(check(nxt_x, nxt_y)) {
154                     BuildGraph(id(i, j), id(nxt_x, nxt_y) + n * m, 1);
155                 }
156                 nxt_x = i + c, nxt_y = j + r;
157                 if(check(nxt_x, nxt_y)) {
158                     BuildGraph(id(i, j), id(nxt_x, nxt_y) + n * m, 1);
159                 }
160                 nxt_x = i + c, nxt_y = j - r;
161                 if(check(nxt_x, nxt_y)) {
162                     BuildGraph(id(i, j), id(nxt_x, nxt_y) + n * m, 1);
163                 }
164                 ++cnt;
165             }
166         }
167     }
168     int ans = 0;
169     while(bfs(s)) {
170         //cout << "!" << endl;
171         int res = dfs(0, 0x7f7f7f7f);
172         ans += res;
173     }
174     //dbg(ans);
175     // for ( int i = 1; i <= n; ++i ) {
176     //     if(vis[i]) {
177     //         int temp = i;
178     //         do {
179     //             if(temp > n) {
180     //                 temp -= n;
181     //             }
182     //             printf("%d ",temp);
183     //             int x = vis[temp];
184     //             vis[temp] = 0;
185     //             temp = x;
186     //         } while (temp != 0);
187     //         puts("");
188     //     }
189     // }
190     printf("%d\n",cnt - ans);
191     return 0;
192 }

View Code

   #include    <   bits/stdc++.h   >  
   #define    dbg(   x   ) cout    <<    #x    <<    "   =   "    << x    << endl  
   #define    eps    1   e   -   8  
   #define    pi    acos(   -   1.0   )  

   using    namespace std   ;  
   typedef    long    long LL   ;  

   const    int inf    =    0x   3f3f3f3f   ;  

   template   <   class T   >   inline    void    read(T    &   res   )  
   {  
          char c   ;T flag   =   1   ;  
          while((c   =   getchar())   <   '   0   '   ||c   >   '   9   '   )if(c   ==   '   -   '   )flag   =-   1   ;res   =c   -   '   0   '   ;  
          while((c   =   getchar())   >=   '   0   '   &&c   <=   '   9   '   )res   =res   *   10   +c   -   '   0   '   ;res   *=flag   ;  
   }  

   namespace _buff    {  
          const    size_t BUFF    =    1    <<    19   ;  
          char    ibuf   [BUFF   ],    *ib    = ibuf   ,    *ie    = ibuf   ;  
          char    getc()    {  
              if    (ib    == ie   )    {  
               ib    = ibuf   ;  
               ie    = ibuf    +    fread(ibuf   ,    1   , BUFF   , stdin   );  
              }  
              return ib    == ie    ?    -   1    :    *ib   ++   ;  
          }  
   }  

   int    qread()    {  
          using    namespace _buff   ;  
          int ret    =    0   ;  
          bool pos    =    true   ;  
          char c    =    getc();  
          for    (;    (c    <    '   0   '    || c    >    '   9   '   )    && c    !=    '   -   '   ; c    =    getc())    {  
              assert(   ~c   );  
          }  
          if    (c    ==    '   -   '   )    {  
           pos    =    false   ;  
           c    =    getc();  
          }  
          for    (; c    >=    '   0   '    && c    <=    '   9   '   ; c    =    getc())    {  
           ret    =    (ret    <<    3   )    +    (ret    <<    1   )    +    (c    ^    48   );  
          }  
          return pos    ? ret    :    -ret   ;  
   }  

   const    int maxn    =    2   e   4    +    7   ;  

   int s   , t   , cnt   ;  
   char    a   [   100   ][   100   ];  
   int    head   [maxn    <<    1   ],    edge   [maxn    <<    1   ],    nxt   [maxn    <<    1   ],    vis   [maxn    <<    1   ];  
   int    w   [maxn    <<    1   ];   //残量网络  
   int    rev   [maxn    <<    1   ];  
   int    depth   [maxn    <<    1   ];   //图层  
   int n   , m   ;  

   inline    int    id(   int    a   ,    int    b   )    {  
          return    (a    -    1   )    * n    + b   ;  
   }  

   inline    void    BuildGraph(   int    u   ,    int    v   ,    int    cap   )    {  
          ++cnt   ;  
          edge   [cnt   ]    = v   ;  
          nxt   [cnt   ]    =    head   [u   ];  
          rev   [cnt   ]    = cnt    +    1   ;  
          w   [cnt   ]    = cap   ;  
          head   [u   ]    = cnt   ;  

          ++cnt   ;  
          edge   [cnt   ]    = u   ;  
          nxt   [cnt   ]    =    head   [v   ];  
          w   [cnt   ]    =    0   ;  
          rev   [cnt   ]    = cnt    -    1   ;  
          head   [v   ]    = cnt   ;  
   }  

   bool    bfs(   int    x   )    {  
       queue   <int> q   ;  
          while(   !   q   .empty())    {  
              q   .pop();  
          }  
          memset(depth   ,    63   ,    sizeof   (depth   ));  
          depth   [s   ]    =    0   ;  
          q   .push(s   );  
          do    {  
              int u    =    q   .front();  
              q   .pop();  
              for    (    int i    =    head   [u   ]; i   ; i    =    nxt   [i   ]    )    {  
                  int v    =    edge   [i   ];  
                  if(   w   [i   ]    >    0    &&    depth   [u   ]    +    1    <    depth   [v   ])    {  
                      depth   [v   ]    =    depth   [u   ]    +    1   ;  
                      q   .push(v   );  
                      if(v    == t   )    {  
                          return    true   ;  
                      }  
                  }  
              }  
          }    while    (   !   q   .empty());  
          return    false   ;  
   }  

   int    dfs(   int    u   ,    int    dist   )    {  
          if(u    == t   )    {  
              return dist   ;  
          }  
          for    (    int i    =    head   [u   ]; i   ; i    =    nxt   [i   ]    )    {  
              int v    =    edge   [i   ];  
              if(   depth   [v   ]    ==    depth   [u   ]    +    1    &&    w   [i   ]    >    0   )    {  
                  int di    =    dfs(v   ,    min(dist   ,    w   [i   ]));  
                  if(di    >    0   )    {  
                      w   [i   ]    -= di   ;  
                      w   [   rev   [i   ]]    += di   ;  
                   //vis[u] = v;  
                   //printf("vis[%d]:%d\n",u, v);  
                      return di   ;  
                  }  
              }  
          }  
          return    0   ;  
   }  

   bool    check(   int    x   ,    int    y   )    {  
          if(x    >=    1    && x    <= m    && y    >=    1    && y    <= n   )    {  
              return    true   ;  
          }  
          return    false   ;  
   }  

   int    main()  
   {  
       //freopen("data.txt", "r", stdin);  
          int r   , c   ;  
          memset(vis   ,    0   ,    sizeof   (vis   ));  
          read(m   );    read(n   );    read(r   );    read(c   );  
       s    =    0   , t    =    2    * n    * m    +    1   ;  
          for    (    int i    =    1   ; i    <= m   ;    ++i    )    {  
              for    (    int j    =    1   ; j    <= n   ;    ++j    )    {  
               cin    >>    a   [i   ][j   ];  
              }  
          }  
          int cnt    =    0   ;  
          for    (    int i    =    1   ; i    <= m   ;    ++i    )    {  
              for    (    int j    =    1   ; j    <= n   ;    ++j    )    {  
                  if(   a   [i   ][j   ]    ==    '   .   '   )    {  
                      BuildGraph(s   ,    id(i   , j   ),    1   );  
                      BuildGraph(id(i   , j   )    + n    * m   , t   ,    1   );  
                      int nxt_x    = i    + r   , nxt_y    = j    + c   ;  
                      if(check(nxt_x   , nxt_y   ))    {  
                          BuildGraph(id(i   , j   ),    id(nxt_x   , nxt_y   )    + n    * m   ,    1   );  
                      }  
                   nxt_x    = i    + r   , nxt_y    = j    - c   ;  
                      if(check(nxt_x   , nxt_y   ))    {  
                          BuildGraph(id(i   , j   ),    id(nxt_x   , nxt_y   )    + n    * m   ,    1   );  
                      }  
                   nxt_x    = i    + c   , nxt_y    = j    + r   ;  
                      if(check(nxt_x   , nxt_y   ))    {  
                          BuildGraph(id(i   , j   ),    id(nxt_x   , nxt_y   )    + n    * m   ,    1   );  
                      }  
                   nxt_x    = i    + c   , nxt_y    = j    - r   ;  
                      if(check(nxt_x   , nxt_y   ))    {  
                          BuildGraph(id(i   , j   ),    id(nxt_x   , nxt_y   )    + n    * m   ,    1   );  
                      }  
                      ++cnt   ;  
                  }  
              }  
          }  
          int ans    =    0   ;  
          while(bfs(s   ))    {  
           //cout << "!" << endl;  
              int res    =    dfs(   0   ,    0x   7f7f7f7f   );  
           ans    += res   ;  
          }  
       //dbg(ans);  
       // for ( int i = 1; i <= n; ++i ) {  
       //     if(vis[i]) {  
       //         int temp = i;  
       //         do {  
       //             if(temp > n) {  
       //                 temp -= n;  
       //             }  
       //             printf("%d ",temp);  
       //             int x = vis[temp];  
       //             vis[temp] = 0;  
       //             temp = x;  
       //         } while (temp != 0);  
       //         puts("");  
       //     }  
       // }  
          printf(   "   %d   \n   "   ,cnt    - ans   );  
          return    0   ;  
   }  