C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 424K, 提交时间: 2023-04-07 22:20:52

// Blossom Algorithm
//0base
#include <bits/stdc++.h>
using namespace std;
struct blossom {
    int n, vis_t;
    vector<vector<int>> E;
    vector<int> match, label, org, vis, parent;
    queue<int> Q;
    blossom(int _n) {
        n = _n;
        E = vector<vector<int>>(n, vector<int>());
        match.assign(n, -1);
        label.resize(n);
        org.resize(n);
        iota(org.begin(), org.end(), 0);
        parent.assign(n, -1);
        vis.assign(n, 0);
        vis_t = 0;
    }
    void addEdge(int u, int v) {
        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }
    auto lca(int v, int u) {
        vis_t++;
        while (true) {
            if (v != -1) {
                if (vis[v] == vis_t) {
                    return v;
                }
                vis[v] = vis_t;
                if (match[v] == -1) {
                    v = -1;
                } else {
                    v = org[parent[match[v]]];
                }
            }
            swap(v, u);
        }
    }
    void agument(int v) {
        while (v != -1) {
            auto pv = parent[v];
            auto nxt = match[pv];
            match[v] = pv;
            match[pv] = v;
            v = nxt;
        }
    }
    void flower(int v, int u, int a) {
        while (org[v] != a) {
            parent[v] = u;
            u = match[v];
            if (label[u] == 1) {
                label[u] = 0;
                Q.emplace(u);
            }
            org[v] = org[u] = a;
            v = parent[u];
        }
    }
    auto bfs(int root) {
        fill(label.begin(), label.end(), -1);
        iota(org.begin(), org.end(), 0);
        while (!Q.empty()) {
            Q.pop();
        }
        Q.emplace(root);
        label[root] = 0;
        while (!Q.empty()) {
            auto u = Q.front();
            Q.pop();
            for (auto v : E[u]) {
                if (label[v] == -1) {
                    label[v] = 1;
                    parent[v] = u;
                    if (match[v] == -1) {
                        agument(v);
                        return true;
                    }
                    label[match[v]] = 0;
                    Q.push(match[v]);
                    continue;
                } else if (label[v] == 0 && org[v] != org[u]) {
                    auto a = lca(org[u], org[v]);
                    flower(v, u, a);
                    flower(u, v, a);
                }
            }
        }
        return false;
    }
    void solve() {
        for (int i = 0; i < n; ++i) {
            if (match[i] == -1) {
                bfs(i);
            }
        }
    }
};
int main()
{
    int n;cin>>n;
    vector<pair<int,int>> a;
    vector<int> g;
    set<int>s;
    int num = 0;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        bool flag=false;
        for(int j=2;j*j<=x;j++)if(x%j==0){
            flag=true;
            if(x!=j*j){
                g.push_back(j);
                g.push_back(x/j);
                a.emplace_back(j,x/j);
            }
            else{
                if(s.find(x)==s.end()){
                    num++;
                    s.insert(x);
                    s.insert(j);
                }
            }
        }
        if(!flag&&s.find(x)==s.end()){
            num++;
            s.insert(x);
            s.insert(x*x);
        }
    }
    sort(g.begin(),g.end());
    g.resize(unique(g.begin(),g.end())-g.begin());
    int siz=(int)g.size();
    blossom G(siz);
    for(auto [x,y]:a)if(s.find(x*x)==s.end()&&s.find(y*y)==s.end()){
        x=lower_bound(g.begin(),g.end(),x)-g.begin();
        y=lower_bound(g.begin(),g.end(),y)-g.begin();
        G.addEdge(x,y);
        // cout<<g[x]<<" "<<g[y]<<"\n";
    }
    int t=0;
    G.solve();
    for (int i = 0; i < siz; ++i) {
        if (G.match[i] != -1) {
            t++;
            // cout<<g[i]<<"\n";
        }
    }
    cout<<num+t/2<<"\n";
    return 0;
}

C++(clang++11) 解法, 执行用时: 19ms, 内存消耗: 2860K, 提交时间: 2021-04-17 16:20:07

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int book[10000007],visit[1005];
int top=1;

vector<int>nxt[1000];
bool e[1000][1000];
int sp;
void dfs(int x)
{
	for(int i=1;i<top;i++)
	{
		if(visit[i])continue;
		if(e[x][i])
		{
			sp++;
			visit[i]=1;
			dfs(i);
		}
	}
}
int main()
{
	int n;
	int ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int xx;
		cin>>xx;
		int x,y;
		for(x=2;x<10000&&x<=xx;x++)
		{
			if(xx%x==0)break;
		}
        if(x==10000)x=xx;
		y=xx/x;
		if(!book[x])book[x]=top++;
		if(!book[y])book[y]=top++;
		if(y==1)
		{
			e[book[x]][book[x]]=1;
		}
		else
		{
			e[book[x]][book[y]]=1;
			e[book[y]][book[x]]=1;
		}
	}
	
	for(int i=1;i<top;i++)
	{
		if(e[i][i]==1)
		{
			ans++;
			for(int j=1;j<top;j++)
			{
				e[i][j]=e[j][i]=0;
			}
		}
	}
//	for(int i=1;i<top;i++,cout<<endl)
//		for(int j=1;j<top;j++)
//		cout<<e[i][j];cout<<endl;
//	cout<<ans<<endl<<endl;;
	while(1)
	{
		bool flag;flag=0;
		for(int i=1;i<=top;i++)
		{
			int sum,up;
			sum=0;
			for(int j=1;j<top;j++)
			{
				sum+=e[i][j];
				if(e[i][j])up=j;
			}
			if(sum==1)
			{
				ans++;
				flag=1;
//				cout<<up<<'-'<<ans<<endl;
				for(int j=1;j<top;j++)
				{
					e[i][j]=e[j][i]=0;
					e[up][j]=e[j][up]=0;
				}
			}
//			for(int i=1;i<top;i++,cout<<endl)
//		for(int j=1;j<top;j++)
//		cout<<e[i][j];
//		cout<<endl;
		}
		if(!flag)break;
		
	}
	int tmp=0;

	for(int i=1;i<=n;i++)
	{
		sp=1;
		visit[i]=1;
		dfs(i);
		ans+=sp/2;
	}
//	ans+=tmp/2;
	cout<<ans;;
}