Merry Christmas :.☆(~▽~)/$:°★

coding还是很暖心的嘛…虽然我不过圣诞节…

懵逼的 题目

最近刷网络流24题…啥都不会…
除了二分图的板子就剩这个题了…
…这tm是网络流???

传送至 Luogu

扯淡的 题解

因为数据服务很小…把有哪些位置有bug压成一个整形, 作为一个状态, 也就是图中的一个点, 补丁看做边, 然后跑最短路就行…..了吗?
因为点最多到(1 << 20)…所以边其实是存不下来的…随机存边失败后…看题解里说…可以每次转移的时候枚举每一条边…emmmmmm….

注意几个问题…好像题解是错的

(x & y) // 如果x中和y中有至少一个重合的元素, 返回true
(x & (~y)) // 如果y中的元素x中一个也没有, 返回true
((x & y) == y) // 如果x包含y中所有的元素, 返回true

沙茶的 代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAXN ((1 << 20) + 5)
#define MAXM (100 + 5)
#define MAXn (20 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define pii pair<int, int>
using namespace std;
struct edg
{
    int cnth;
    int msth;
    int mbug;
    int lbug;
    int cost;
    edg() {}
    edg(int c, int m, int mo, int l, int co): cnth(c), msth(m), mbug(mo), lbug(l), cost(co) {}
} b[MAXM];
bool inq[MAXN];

struct cmp
{
    bool operator () (const pii x, const pii y)
    {
        return x.second > y.second;
    }
};

int n;
int km;
int s, t = 0;
int ans = 0;
int dis[MAXN];
void init();
void spfa(int);
inline bool pd(int, int);
int main()
{
    init();
//    dijk(s);
    spfa(s);
    if (ans < INF)
        printf("%d", ans);
    else
        puts("0");
    return 0;
}
void init()
{
    scanf("%d%d", &n, &km);
    s = (1 << n) - 1;
    char sx[MAXn], sy[MAXn];
    int cnth, msth, mbug, lbug;
    int src;
    for (int i = 1; i <= km; i++)
    {
        scanf("%d", &src);
        scanf("%s%s", sx, sy);
        cnth = msth = mbug = lbug = 0;
        for (int j = 0; j < n; j++)
        {
            cnth <<= 1, msth <<= 1, mbug <<= 1, lbug <<= 1;
            if (sx[j] == '+')
            {
                msth |= 1;
            }
            else if (sx[j] == '-')
            {
                cnth |= 1;
            }
            if (sy[j] == '-')
            {
                lbug |= 1;
            }
            else if (sy[j] == '+')
            {
                mbug |= 1;
            }
        }
        b[i] = edg(cnth, msth, mbug, lbug, src);
    }
}

void spfa(int start)
{
    memset(inq, false, sizeof(inq));
    memset(dis, 0x7f, sizeof(dis));
    queue<int> q;
    q.push(start);
    dis[start] = 0;
    inq[start] = true;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (int i = 1; i <= km; i++)
        {
            if (pd(dq, i))
            {
                int bt = ((dq & (~(b[i].lbug))) | b[i].mbug);
                if (dis[bt] > dis[dq] + b[i].cost)
                {
                    dis[bt] = dis[dq] + b[i].cost;
                    if (!inq[bt])
                    {
                        q.push(bt);
                        inq[bt] = true;
                    }
                }
            }

        }
    }
    ans = dis[t];
}
inline bool pd(int dq, int i)
{
    if ((dq & b[i].msth) != b[i].msth)
        return false;
    if (dq & b[i].cnth)
        return false;
    return true;
}

/*
2 4
1 +- --
0 -0 0+
1 0+ 0-
0 +- 00
*/

By 啥都不会的 Cansult