P2761 软件补丁问题【状压】【最短路】

输入输出样例

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

3 3
1 000 00-
1 00- 0-+
2 0-- -++

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

8

思路
　　为啥会有网络流的tag
　　wa了5发感觉怎么建图都不对
　　一看都是状压最短路
　　打了个dijRE了
　　发现好像边太多
　　看别人都用的spfa莽，干脆我也莽一发好了
　　大家都知道spfa的核心就是边建图边松弛
　　如何建图：
　　　　因为对于第 i 个错误来说，只存在‘待修复’和‘已修复’两种状态
　　　　为了方便枚举，对状态进行压缩成一个整数来枚举
　　　　因为可能成环，显然状压dp很难处理这类问题
　　　　考虑用spfa来解决
　　　　对于每个错误，来枚举每个可能和他连的边
　　　　只要当前点 u 和 b1[i] 与运算为 b1[i] ，并且与 b2[i] 与为 0 说明此错误满足要求
　　　　再判断这条边的终点
　　　　先让 u 与 f1[i] 或（这里一定要先或因为后面要和 f1[i] 异或来使 u 上 f1[i] 的范围都清0）再与 f2[i] 或最后和 f1[i] 异或来清零这个区间
　　　　
　　松弛就没啥好说的了，毕竟起终点都确立下来了

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 = 0x7f7f7f7f;
 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 = 1e6 + 7;
 49 
 50 int n, m;
 51 
 52 int b1[maxn], b2[maxn], f1[maxn], f2[maxn];
 53 int dis[maxn], val[maxn];
 54 bool vis[maxn];
 55 
 56 int spfa(int s) {
 57     memset(vis, 0, sizeof(vis));
 58     memset(dis, 127, sizeof(dis));
 59     dis[s] = 0;
 60     queue<int> q;
 61     while(!q.empty()) {
 62         q.pop();
 63     }
 64     q.push(s);
 65     while(!q.empty()) {
 66         int u = q.front();
 67         q.pop();
 68         int v = 0;
 69         vis[u] = false;
 70         for ( int i = 1; i <= m; ++i ) {
 71             if((b1[i] & u) == b1[i] && (b2[i] & u) == 0) {
 72                 v = ((u | f1[i]) | f2[i]) ^ f1[i];
 73                 if(dis[u] + val[i] < dis[v]) {
 74                     dis[v] = dis[u] + val[i];
 75                     if(!vis[v]) {
 76                         vis[v] = true;
 77                         q.push(v);
 78                     }
 79                 }
 80             }
 81         }
 82     }
 83     //dbg(dis[0]);
 84     return dis[0];
 85 }
 86 
 87 int main()
 88 {
 89     read(n); read(m);
 90     for ( int i = 1; i <= m; ++i ) {
 91         read(val[i]);
 92         string b, f;
 93         cin >> b;
 94         cin >> f;
 95         b1[i] = b2[i] = f1[i] = f2[i] = 0;
 96         for ( int j = 0; j < n; ++j ) {
 97             if(b[j] == '+') {
 98                 b1[i] |= (1 << j);
 99             }
100             else if(b[j] == '-') {
101                 b2[i] |= (1 << j);
102             }
103             if(f[j] == '-') {
104                 f1[i] |= (1 << j);
105             }
106             else if(f[j] == '+') {
107                 f2[i] |= (1 << j);
108             }
109         }
110     }
111     int ans = spfa((1 << n) - 1);
112     if(ans == inf) {
113         cout << 0 << endl;
114     }
115     else {
116         cout << dis[0] << endl;
117     }
118     return 0;
119 }

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   7f7f7f7f   ;  

   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    =    1   e   6    +    7   ;  

   int n   , m   ;  

   int    b1   [maxn   ],    b2   [maxn   ],    f1   [maxn   ],    f2   [maxn   ];  
   int    dis   [maxn   ],    val   [maxn   ];  
   bool    vis   [maxn   ];  

   int    spfa(   int    s   )    {  
          memset(vis   ,    0   ,    sizeof   (vis   ));  
          memset(dis   ,    127   ,    sizeof   (dis   ));  
          dis   [s   ]    =    0   ;  
       queue   <int> q   ;  
          while(   !   q   .empty())    {  
              q   .pop();  
          }  
          q   .push(s   );  
          while(   !   q   .empty())    {  
              int u    =    q   .front();  
              q   .pop();  
              int v    =    0   ;  
              vis   [u   ]    =    false   ;  
              for    (    int i    =    1   ; i    <= m   ;    ++i    )    {  
                  if((   b1   [i   ]    & u   )    ==    b1   [i   ]    &&    (   b2   [i   ]    & u   )    ==    0   )    {  
                   v    =    ((u    |    f1   [i   ])    |    f2   [i   ])    ^    f1   [i   ];  
                      if(   dis   [u   ]    +    val   [i   ]    <    dis   [v   ])    {  
                          dis   [v   ]    =    dis   [u   ]    +    val   [i   ];  
                          if(   !   vis   [v   ])    {  
                              vis   [v   ]    =    true   ;  
                              q   .push(v   );  
                          }  
                      }  
                  }  
              }  
          }  
       //dbg(dis[0]);  
          return    dis   [   0   ];  
   }  

   int    main()  
   {  
          read(n   );    read(m   );  
          for    (    int i    =    1   ; i    <= m   ;    ++i    )    {  
              read(   val   [i   ]);  
           string b   , f   ;  
           cin    >> b   ;  
           cin    >> f   ;  
              b1   [i   ]    =    b2   [i   ]    =    f1   [i   ]    =    f2   [i   ]    =    0   ;  
              for    (    int j    =    0   ; j    < n   ;    ++j    )    {  
                  if(   b   [j   ]    ==    '   +   '   )    {  
                      b1   [i   ]    |=    (   1    << j   );  
                  }  
                  else    if(   b   [j   ]    ==    '   -   '   )    {  
                      b2   [i   ]    |=    (   1    << j   );  
                  }  
                  if(   f   [j   ]    ==    '   -   '   )    {  
                      f1   [i   ]    |=    (   1    << j   );  
                  }  
                  else    if(   f   [j   ]    ==    '   +   '   )    {  
                      f2   [i   ]    |=    (   1    << j   );  
                  }  
              }  
          }  
          int ans    =    spfa((   1    << n   )    -    1   );  
          if(ans    == inf   )    {  
           cout    <<    0    << endl   ;  
          }  
          else    {  
           cout    <<    dis   [   0   ]    << endl   ;  
          }  
          return    0   ;  
   }  