285484026

「网络流 24 题」软件补丁
「网络流 24 题」软件补丁题解:这个出题人描述有一点问题,更好理解的表述是:对于一个软件包有N个错误,然后如果这...
扫描右侧二维码阅读全文
25
2018/10

「网络流 24 题」软件补丁

「网络流 24 题」软件补丁
题解:这个出题人描述有一点问题,更好理解的表述是:对于一个软件包有N个错误,然后如果这个N个错误中含有B1集合这些编号的错误,而不含有B2集合编号的错误,那么就可以消除F1集合编号的错误,但同时会加上F2集合编号的错误。实际上只有一个问题集合
建模:这个题目实际上不用网络流,直接用spfa跑就可以了。用状态压缩表示是否存在某个编号的错误

#include <bits/stdc++.h>
#define mp make_pair 
#define pb push_back

const int MAXN = 1200000,MAXM = 25,INF = 1000000000;

using namespace std;

int n,m,d[MAXN],dis[MAXN];
char a[MAXN],b[MAXN];
bool inq[MAXN];

struct node{
    int a,b,c,d,v;
}edge[MAXN];

inline void init()
{
    scanf("%d%d",&n,&m);
    int v,len;
    for(int i = 1;i <= m;i++){
        scanf("%d",&v);
        scanf("%s %s",a,b);
        len = strlen(a);
        for(int j = 0;j < len;j++){
        if(a[j] == '+') edge[i].a += d[j];
        if(a[j] == '-') edge[i].b += d[j];  
        }
        for(int j = 0;j < len;j++){
        if(b[j] == '-') edge[i].c += d[j];
        if(b[j] == '+') edge[i].d += d[j];  
        }
        edge[i].v = v;
    }
}

queue<int>Q;

inline void spfa(){
    for(int i = 0;i <= d[n]-1;i++) dis[i] = INF;
    Q.push(d[n]-1);dis[d[n]-1] = 0;inq[d[n]-1] = true;
    while(!Q.empty())
    {
        int x = Q.front();Q.pop();inq[x] = false;
        for(int i = 1;i <= m;i++)
        {
            if((x&edge[i].a) == edge[i].a && !(x&edge[i].b)){
                int v = x - (x&edge[i].c);v |= edge[i].d;
                if(dis[v] > dis[x] + edge[i].v){
                    dis[v] = dis[x] + edge[i].v;
                    if(!inq[v]){
                        Q.push(v);
                        inq[v] = true;
                    }
                }
            } 
        } 
    }
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    d[0] = 1;
    for(int i = 1;i <= 20;i++) d[i] = d[i-1] << 1; 
    init();
    spfa();
    if(dis[0] == INF) printf("0\n");
    else printf("%d\n",dis[0]);
    return 0;
}
Last modification:October 25th, 2018 at 02:05 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment