【poj2724】 Purifying Machine

时间：2023-03-10 05:26:50
【poj2724】 Purifying Machine

http://poj.org/problem?id=2724 (题目链接)

题意

　　Mike有一个机器可以帮助他清理奶酪，每个奶酪由一个n位二进制数表示，机器上一共有n个按钮，每个按钮有1，0，＊，其中‘＊’表示既可以是1也可以是0。每次操作都可以命令机器生成一个二进制数。因此机器可以表示出一个或两个二进制数，这样就可以清理奶酪了。现在问要清理m块n位的二进制奶酪需要操作多少次。

Solution

　　如果两个奶酪只有一位不同，那么就可以通过一次操作将两个都消掉，这样的奶酪当然是越多越好，因此，很容易就想到了二分图匹配求最小路径覆盖。如果两个奶酪的二进制数只有一位不同，就将这两个连边。所以先去重，再连边，连完边后跑匈牙利就可以了。

　　刚开始用string写的，结果莫名其妙的Wa，调试还看不到，改成char就A了，可惜代码丑了许多。

代码

// poj2724

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<string>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    int f,x=0;char ch=getchar();

    while (ch<='0' || ch>'9') {if (ch=='-') f=-1;else f=1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=10010;

struct edge {int to,next;}e[maxn<<2];

int n,m,head[maxn],vis[maxn],p[maxn],cnt;

//string s[maxn];

char s[maxn][10];

bool cmp(int x,int y) {

    int tot=0;

    for (int i=0;i<n;i++)

        if (s[x][i]!=s[y][i]) {tot++;if (tot>1) return 0;}

    return 1;

}

void insert(int u,int v) {

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

}

bool find(int x) {

    for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) {

            vis[e[i].to]=1;

            if (p[e[i].to]==0 || find(p[e[i].to])) {

                    p[e[i].to]=x;

                    return 1;

            }

        }

    return 0;

}

void check(int x) {

    for (int i=0;i<n;i++) if (s[x][i]=='*') {

            s[x][i]='1';m++;

            for (int j=0;j<n;j++) s[m][j]=s[x][j];

            s[m][i]='0';

        }

}

int main() {

    int M;

    while (scanf("%d%d",&n,&M)!=EOF && n && M) {

        m=0;cnt=0;

        for (int i=1;i<=M;i++) {

            m++;

            cin>>s[m];

            check(m);

        }

        int x=0;

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

            int flag=0;

            for (int j=1;j<=x;j++) {

                flag=1;

                for (int k=0;k<n;k++) if (s[i][k]!=s[j][k]) {flag=0;break;}

                if (flag) break;

            }

            if (!flag) memcpy(s[++x],s[i],sizeof(s[i]));

        }

        m=x;

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

            for (int j=1;j<=m;j++)

                if (i!=j && cmp(i,j)) insert(i,j);

        int ans=0;

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

            for (int j=1;j<=m;j++) vis[j]=0;

            if (find(i)) ans++;

        }

        printf("%d\n",m-ans/2);

        for (int i=1;i<=m;i++) p[i]=head[i]=0;

    }

    return 0;

}

　　

相关文章