1 条题解
-
0
// 德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱德丽莎你好可爱 // 德丽莎的可爱在于德丽莎很可爱,德丽莎为什么很可爱呢,这是因为德丽莎很可爱! // 没有力量的理想是戏言,没有理想的力量是空虚 #include <bits/stdc++.h> #define LL long long #define int long long using namespace std; char ibuf[1 << 15], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++) inline int read() { char ch = getchar(); int x = 0, f = 1; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return x * f; } void print(LL x) { if (x > 9) print(x / 10); putchar(x % 10 + '0'); } template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; } #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define repd(i, l, r) for (int i = (l); i >= (r); i--) #define REP(i, l, r) for (int i = (l); i < (r); i++) const int N = 5e6; int pr[N], cnt, vis[N]; void prime(int n) { rep (i, 2, n) { if (!vis[i]) { pr[++cnt] = i; } for (int j = i; j <= n; j += i) vis[j] = 1; } } int n1, n2; map <pair<int,int>, int> id; int tot, S, T; int num = 1, nex[N], first[N], v[N], flow[N]; vector <int> ys[205]; int dep[N], cur[N]; queue <int> q; struct node { int a, b, c; } X[N], Y[N]; bool bfs(int s,int t) { rep (i, 0, t) dep[i] = 0; q.push(s); dep[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); cur[u] = first[u]; for (int i = first[u]; i; i = nex[i]) { int to = v[i]; if (dep[to] || !flow[i]) continue; q.push(to); dep[to] = dep[u] + 1; cur[to] = first[to]; } } return dep[t] != 0; } int dfs(int x,int a) { if (x == T) return a; int ans = 0; for (int i = cur[x]; i; i = nex[i]) { int to = v[i]; cur[x] = i; if (dep[to] == dep[x] + 1 && flow[i]) { int qwq = dfs(to, min(flow[i], a)); a -= qwq; flow[i] -= qwq; flow[i ^ 1] += qwq; ans += qwq; if (!a) break; } } return ans; } int mxflow(int s,int t) { int ans = 0; while (bfs(s, t)) ans += dfs(s, 1ll << 30); return ans; } void add(int from,int to,int val) { nex[++num] = first[from]; first[from] = num; v[num] = to; flow[num] = val; } void ins(int a,int b,int c) { add(a, b, c), add(b, a, 0); } void solve() { prime(200); n1 = read(), n2 = read(); rep (i, 1, n1) { X[i].a = read(), X[i].b = read(), X[i].c = read(); } rep (i, 1, n2) { Y[i].a = read(), Y[i].b = read(), Y[i].c = read(); } tot = n1 + n2; sort(pr + 1, pr + cnt + 1); rep (x, 1, 200) { rep (j, 1, cnt) { if (x < pr[j]) continue; if (x % pr[j] == 0) ys[x].push_back(pr[j]); } } // AB id.clear(); rep (i, 1, n1) { int A = X[i].a, B = X[i].b; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[{pp, qq}] == 0) { id[ {pp, qq} ] = ++tot; // cout << 1 << " " << pp << " " << qq << " get id : " << tot << "\n"; } int pt = id[ {pp, qq} ]; ins(i, pt, 1); } } } rep (i, 1, n2) { int A = Y[i].a, B = Y[i].b; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[ {pp, qq} ] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(pt, i + n1, 1); } } } // AC id.clear(); rep (i, 1, n1) { int A = X[i].a, B = X[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[{pp, qq}] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(i, pt, 1); } } } rep (i, 1, n2) { int A = Y[i].a, B = Y[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[ {pp, qq} ] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(pt, i + n1, 1); } } } //BC id.clear(); rep (i, 1, n1) { int A = X[i].b, B = X[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[{pp, qq}] == 0) id[ {pp, qq} ] = ++tot; int pt = id[ {pp, qq} ]; ins(i, pt, 1); } } } rep (i, 1, n2) { int A = Y[i].b, B = Y[i].c; for (auto p : ys[A]) { for (auto q : ys[B]) { int pp = p, qq = q; if (id[ {pp, qq} ] == 0) { id[ {pp, qq} ] = ++tot; } int pt = id[ {pp, qq} ]; ins(pt, i + n1, 1); } } } S = tot + 1, T = tot + 2; rep (i, 1, n1) ins(S, i, 1); rep (i, 1, n2) ins(i + n1, T, 1); int ans = mxflow(S, T); cout << ans << "\n"; } signed main () { #ifdef LOCAL_DEFINE freopen("1.in", "r", stdin); freopen("1.ans", "w", stdout); #endif int T = 1; while (T--) solve(); #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }
- 1
信息
- ID
- 4205
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 70
- 已通过
- 26
- 上传者