UVa 1663 净化器

题意：

给m个长度为n的模板串，每个模板串包含字符0,1和最多一个星号"*"，其中星号可以匹配0或1。例如，模板01*可以匹配010和011两个串。改写这个模板集合，使得模板的个数最少。

思路：

一个模板只能匹配两个字符串。所以要减少次数的话，我们就要尽量把字符串一一配对，这样每两个字符串都可以用一个模板串来表示。那么这就很明显的是求二分图的最大匹配。下面的代码中因为重复匹配了，所以最后需要除2。

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 int n, m;

 int c[maxn];

 int g[maxn][maxn];

 int vis[maxn];

 int match[maxn];

 int dfs(int x)

 {

     for (int i = ; i < maxn; i++)

     {

         if (g[x][i] && !vis[i])

         {

             vis[i] = ;

             if (match[i] == - || dfs(match[i]))

             {

                 match[i] = x;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     char s[];

     ios::sync_with_stdio(false);

     //freopen("D:\\txt.txt", "r", stdin);

     while (~scanf("%d%d",&n,&m)&&(n||m))

     {

         memset(c, , sizeof(c));

         memset(g, , sizeof(g));

         for (int i = ; i < m; i++)

         {

             int num= ;

             int pos = -;

             scanf("%s", s);

             for (int j = ; j < n; j++)

             {

                 if (s[j] == '')  num |=  << j;

                 else if (s[j] == '*')   pos = j;

             }

             c[num] = ;

             if (pos != -)

             {

                 num |=  << pos;

                 c[num] = ;

             }

         }

         int cnt = ;

         for (int i = ; i < maxn; i++)

         {

             if (c[i])

             {

                 cnt++;

                 for (int j = ; j < n; j++)

                 {

                     int temp = i ^ ( << j);

                     if (c[temp])  g[i][temp] = ;

                 }

             }

         }

         int tot = ;

         memset(match, -, sizeof(match));

         for (int i = ; i < maxn; i++)

         {

             memset(vis, , sizeof(vis));

             tot += dfs(i);

         }

         cout << cnt - tot /  << endl;

     }

 }

巴特西

UVa 1663 净化器

最新文章

热门文章