[网络流24题] 洛谷P2761 软件补丁问题

题意：某公司发现其研制的一个软件中有 n个错误，随即为该软件发放了一批共 m 个补丁程序。对于每一个补丁 i ，都有 2 个与之相应的错误集合 B1(i)和 B2(i)，使得仅当软件包含 B1(i)中的所有错误，而不包含 B2(i)中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1(i)，而同时加入另一些错误 F2(i)。另外，每个补丁都耗费一定的时间。试设计一个算法，利用公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。

虽然是网络流24题，但是这题好像应该用最短路来做。

把20个bug状态压缩成二进制表示，然后跑Dijkstra最短路即可。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

const int N=;

const int INF=0x3f3f3f3f;

int n,m;

struct bug{

    int tim;

    char p[],q[];

}a[N];

bool check(int now,int k) {

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

        if (a[k].p[i]=='+' && !(now&(<<i)) || a[k].p[i]=='-' && (now&(<<i))) return ;

    return ;

}

int change(int now,int k) {

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

        if (a[k].q[i]=='-') now=now&(~(<<i));

        if (a[k].q[i]=='+') now=now|(<<i);

    }

    return now;

}

int d[<<];

priority_queue<pii> q;

int Dijkstra() {

    memset(d,0x3f,sizeof(d));

    d[(<<m)-]=;

    q.push(make_pair(,(<<m)-));

    while (!q.empty()) {

        pii x=q.top(); q.pop();

        if (d[x.second]!=-x.first) continue;

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

            if (check(x.second,i)) {

                int y=change(x.second,i);

                if (d[x.second]+a[i].tim<d[y]) {

                    d[y]=d[x.second]+a[i].tim;

                    q.push(make_pair(-d[y],y));

                }

            }

    }

    return d[]==INF ?  : d[];

}

int main()

{

    scanf("%d%d",&m,&n);

    for (int i=;i<=n;i++) scanf("%d%s%s",&a[i].tim,&a[i].p,&a[i].q);

    cout<<Dijkstra()<<endl;

    return ;

}

巴特西

[网络流24题] 洛谷P2761 软件补丁问题

最新文章

热门文章