LG P2065 [TJOI2011]卡片

题目传送门

一道很妙的网络流建图题

网络流代码只有普及难度，真正重要的地方在于建图——鲁迅

Description

给你两组卡片，卡片有权值，只有两种颜色不同卡片的最大公约数大于 \(1\) 时才可以匹配，问最多能匹配多少对。 \(T\) 组数据。

Solution

用网络流来做应该比较好想。

一种朴素的做法是：

• 源点连向所有的红色卡片，所有蓝色卡片连向汇点，流量为 \(1\)。表示所有的卡片都能选一次。
• \(O(nm)\) 遍历所有卡片对，求出他们的 \(\text{gcd}\) 判断，暴力连边。

跑一个最大流就好了。

只能拿 \(70 \texttt{pts}\) 数据还是水。

发现上面的局限在于建图所用的时间是 \(O(nm)\)，还要加上求 \(\gcd\) 的耗时。

考虑到 \(\text{gcd}\) 和质因数有关，考虑对每个卡片进行分解质因数。

让每个红色卡片连向它们的所有质因数，让每个蓝色卡片的所有质因数连向它们自己。

连边方式：源点 \(\to\) 红色卡片 \(\to\) 质因数 \(\to\) 蓝色卡片 \(\to\) 汇点。

所以根本就不用 ISAP。

Tips/Trick

• 质因数要筛到 \(10^7\)，不要贪图复杂度筛到 \(\sqrt{10^7}\)。如果有两个大质数你就挂了；
• 源点和汇点的选择不要与中间点重复；
• 多测要清空（显然这道题只需要清空 head 数组和记录边数的变量。

剩下的看代码吧。

Code

/*
Work by: Suzt_ilymics
Problem: P2065 [TJOI2011]卡片
Knowledge: 网络流Dinic弧优化 
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< q;
    q.push(s), dis[s] = 0, cur[s] = head[s];
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if(e[i].w && dis[v] == -1) {
                dis[v] = dis[u] + 1;
                cur[v] = head[v];
                q.push(v);
                if(v == t) return true;
            }
        }
    }
    return false;
}

int dfs(int u, int limit) {
    if(u == t) return limit;
    int flow = 0;
    for(int i = cur[u]; i && flow < limit; i = e[i].nxt) {
        cur[u] = i; int v = e[i].to;
        if(e[i].w && dis[v] == dis[u] + 1) {
            int f = dfs(v, min(e[i].w, limit - flow));
            if(!f) dis[v] = INF;
            e[i].w -= f, e[i ^ 1].w += f;
            flow += f; 
        }
    }
    return flow;
}

int Dinic() {
    int maxflow = 0, flow = 0;
    while(bfs()) while(flow = dfs(s, INF)) maxflow += flow;
    return maxflow;
} 

void clear() {
    for(int i = 1; i <= t; ++i) head[i] = 0; 
    num_edge = 1;
}

void Init(int limit) {
    for(int i = 2; i <= limit; ++i) {
        if(!vis[i]) tmp[++ Cnt] = i;
        for(int j = 1; j <= Cnt && i * tmp[j] <= limit; ++j) {
            vis[i * tmp[j]] = true;
            if(i % tmp[j] == 0) break; 
        }
    }
//    cout<