时间戳

首页 > 技术文章 > 卡牌配对

卡牌配对

2016gdgzoi509 2019-07-09 22:35 原文

题目

传送门

题解

此题非常坑人， 不仔细看三四遍题目就很容易搞错出题人的意思

所为“至多一项属性值使得两张卡牌该项属性值互质”， 就是至少两项属性值有公共质因数。

直接的想法是暴力枚举连边， 然后二分图匹配。 由于是分层图， dinic可以跑的很快。

再看一下匹配的条件， 我们发现可以可以在图中间加一排点， 每个点表示一个素数对\((p_1, \; p_2)\)， 对于每张卡牌\((A, B, C)\)， 满足\((p_1|A, \; p_2|B)\)或\((p_1|B, \; p_2|C)\)或\((p_1|A, \; p_2|C)\), 那么可在这两点间连一条边。

再跑dinic就能过。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

#include <vector>
#include <queue>

using namespace std;


const int INF = 0x7F7F7F7F;


const int N = 70010, M = 2000010;


int n1, n2;


struct edge
{
    int from, to, flow, cap;
    edge() { }
    edge(int _1, int _2, int _3, int _4) : from(_1), to(_2), flow(_3), cap(_4) { }
};


struct Dinic
{
    edge edges[M];
    int head[N], nxt[M], tot;

    inline void init()
    {
        memset(head, -1, sizeof(head));
        tot = 0;
    }

    inline void add_edge(int x, int y, int z)
    {
        edges[tot] = edge(x, y, 0, z);
        nxt[tot] = head[x];
        head[x] = tot++;
        edges[tot] = edge(y, x, 0, 0);
        nxt[tot] = head[y];
        head[y] = tot++;
    }

    int s, t;

    int cur[N];

    int d[N];
    queue <int> q;

    bool bfs()
    {
        while (!q.empty()) q.pop();
        
        memset(cur, -1, sizeof(cur));
        memset(d, -1, sizeof(head));
        q.push(s);
        d[s] = 0;
        
        while (!q.empty())
        {
            int x = q.front(); q.pop();
            cur[x] = head[x];
            for (int i = head[x]; ~i; i = nxt[i])
            {
                edge & e = edges[i];
                if (e.flow < e.cap && d[e.to] == -1)
                {
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        
        return d[t] == -1 ? 0 : 1;
    }

    int dfs(int x, int a)
    {
        if (x == t || a == 0) return a;
        
        int f = 0, flow = 0;
        for (int & i = cur[x]; ~i; i = nxt[i])
        {
            edge & e = edges[i];
            if (d[e.to] == d[x] + 1 && (f = dfs(e.to, min(e.cap - e.flow, a))) > 0)
            {
                e.flow += f;
                edges[i^1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        
        return flow;
    }

    int maxflow(int _s, int _t)
    {
        s = _s, t = _t;
        int flow = 0;
        while (bfs())
            flow += dfs(s, INF);
        return flow;
    }
} dinic;


vector <int> vec[210];

int id[50][50];

bool vis[210];
int p[210], total;

void Init()
{
    total = 0;
    
    memset(vis, 0, sizeof(vis));
    
    vis[1] = 1;
    for (int i = 2; i <= 200; i++)
    {
        if (!vis[i]) p[++total] = i;
        for (int j = 1; j <= total && p[j] * i <= 200; j++)
        {
            vis[p[j] * i] = 1;
            if (i % p[j] == 0) break;
        }
    }

    for (int i = 1; i <= 200; i++)
    {
        int x = i;
        for (int j = 1; j <= total && x > 1; j++)
            if (x % p[j] == 0)
            {
                vec[i].push_back(j);
                while (x % p[j] == 0)
                    x /= p[j];
            }
    }
    
    for (int i = 1; i <= total; i++)
        for (int j = 1; j <= total; j++)
            id[i][j] = (i-1) * total + j;
}


struct Data
{
    int A, B, C;
    Data() { }
    Data(int _1, int _2, int _3) : A(_1), B(_2), C(_3) { }
} a[2 * N], b[2 * N];


int main()
{
    scanf("%d %d", &n1, &n2);
    for (int i = 1; i <= n1; i++)
        scanf("%d %d %d", &a[i].A, &a[i].B, &a[i].C);
    for (int i = n1+1; i <= n1+n2; i++)
        scanf("%d %d %d", &b[i].A, &b[i].B, &b[i].C);
    
    Init();

    dinic.init();

    int S = n1+n2 + 46*46*3 + 1, T = S + 1;
    for (int i = 1; i <= n1; i++)
        dinic.add_edge(S, i, 1);
    for (int i = n1+1; i <= n1+n2; i++)
        dinic.add_edge(i, T, 1);
    for (int i = 1; i <= n1; i++)
    {
        int A = a[i].A, B = a[i].B, C = a[i].C;
        for (auto v1 : vec[A])
            for (auto v2 : vec[B]) dinic.add_edge(i, n1+n2 + id[v1][v2], INF);
        for (auto v1 : vec[B])
            for (auto v2 : vec[C]) dinic.add_edge(i, n1+n2 + id[v1][v2] + 46*46, INF);
        for (auto v1 : vec[A])
            for (auto v2 : vec[C]) dinic.add_edge(i, n1+n2 + id[v1][v2] + 46*46*2, INF);
    }
    for (int i = n1+1; i <= n1+n2; i++)
    {
        int A = b[i].A, B = b[i].B, C = b[i].C;
        for (auto v1 : vec[A])
            for (auto v2 : vec[B]) dinic.add_edge(n1+n2 + id[v1][v2], i, INF);
        for (auto v1 : vec[B])
            for (auto v2 : vec[C]) dinic.add_edge(n1+n2 + id[v1][v2] + 46*46, i, INF);
        for (auto v1 : vec[A])
            for (auto v2 : vec[C]) dinic.add_edge(n1+n2 + id[v1][v2] + 46*46*2, i, INF);
    }

    printf("%d\n", dinic.maxflow(S, T));
    
    return 0;
}

推荐阅读