SRM 633 div2 1000

又是G家猥琐的题

我采用了暴力搜索的办法, 当然要根据以下性质剪枝:

对任意两个整数x, y

x*y=gcd(x, y)*lcm(x, y)

利用这个剪枝, 如果所有的连通组件都能访问到就是有解了

代码中第一次DFS找出所有连通组件, 第二次则是尝试访问所有点

写出代码

..:

#include <bits/stdc++.h>
using namespace std;
struct edg {
    int n, g, l;
    edg(int _n, int _g, int _l) { n=_n, g=_g, l=_l; }
};
struct cmp {
    int s, h;
    cmp(int _s, int _h) { s=_s, h=_h; }
};
typedef vector<edg> ve;
typedef vector<cmp> vc;
#define pb push_back
#define ret return

int f, t;
int w[501];
int v[501];
ve  g[501];
vc  c;
inline int dfs1(int x) {
    v[x]=1;
    int r=1;
    for (edg e : g[x]) if (!v[e.n]) r+=dfs1(e.n);
    ret r;
}
inline int dfs2(int x, int c, int p) {
    v[x]=1;
    w[x]=c;
    int r=1;
    for (edg e : g[x]) if (e.n!=p) {
        int p=e.g*e.l;
        if (v[e.n]) {
            if (c*w[e.n]!=p || __gcd(c, w[e.n])!=e.g) ret 0;
        } else {
            if (p%c==0 && __gcd(c, p/c)==e.g)
                r+=dfs2(e.n, p/c, x);
            else
                ret 0;
        }
    }
    ret r;
}
class GCDLCMEasy {
public:
    string possible(int n, vector <int> A, vector <int> B, vector <int> G, vector <int> L) {
        for (int i=0; i<A.size(); i++) {
            g[A[i]].pb(edg(B[i], G[i], L[i]));
            g[B[i]].pb(edg(A[i], G[i], L[i]));
        }
        for (int i=0; i<n; i++) if (!v[i]) c.pb(cmp(i, dfs1(i)));
        memset(v, 0, sizeof v);
        f=1;
        for ( ; f && t<c.size(); t++) if (!g[c[t].s].empty()) {
            f=0;
            edg& e=g[c[t].s][0];
            int  p=e.g*e.l;
            for (int i=1; i<=p; i++) if (p%i==0 && __gcd(i, p/i)==e.g) {
                w[c[t].s]=i;
                if (dfs2(c[t].s, i, -1)==c[t].h) {
                    f=1;
                    break;
                } else {
                    memset(v, 0, sizeof v);
                }
            }
        }
        ret f ? "Solution exists" :
                "Solution does not exist";
    }
};