10.12美团笔试第3题

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define bug(x) cout<<#x<<" is "<<x<<endl
const int INF = 0x3f3f3f3f;
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e2;
int n, m;
ll e[N+7][N+7];

//KM
ll mat[N+7],d[N+7],va[N+7],vb[N+7],ak[N+7],bk[N+7];
ll Dfs(ll u){
    va[u]=1;
    for(ll v=1;v<=n;v++)if(!vb[v]){
        if(ak[u]+bk[v]-e[u][v]==0){
            vb[v]=1;
            if(!mat[v]||Dfs(mat[v])) return mat[v]=u,1;
        } else d[v]=min(d[v],ak[u]+bk[v]-e[u][v]);
    }
    return 0;
} 
ll KM(){
    fill(ak+1,ak+n+1,-INF);
    for(ll u=1;u<=n;u++)
        for(ll v=1;v<=n;v++) ak[u]=max(ak[u],e[u][v]);
    for(ll u=1;u<=n;u++){
        while(true){
            fill(va+1,va+n+1,0);
            fill(vb+1,vb+n+1,0);
            fill(d+1,d+n+1,INF);
            if(Dfs(u)) break;
            ll c=INF;
            for(ll v=1;v<=n;v++)if(!vb[v]) c=min(c,d[v]);
            for(ll v=1;v<=n;v++)if(va[v]) ak[v]-=c;
            for(ll v=1;v<=n;v++)if(vb[v]) bk[v]+=c;         
        }
    }
    ll res=0;
    for(ll v=1;v<=n;v++) res+=e[mat[v]][v]; 
    return res;
}
int check(int x){
    if(x == 1) return 0;
    for(int y = 2; y * y <= x; y++){
        if(x % y == 0) return 0;
    }
    return 1;
}
int a[N], b[N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1; j <= m; j++) e[i][j] = INF;
    }
    for(int i = 1; i <= n; i++){
        int fx = check(a[i]);
        for(int j = 1; j <= m; j++){
            int fy = check(b[j]);
            if(fx && fy) e[i][j] = 2 * (a[i] + b[j]);
            else if(fx || fy) e[i][j] = 2 * max(a[i], b[j]);
            else e[i][j] = a[i] + b[j];

            //bug(e[i][j]);
        }
    }
    cout << KM() << endl;
    for(int i = 1; i <= n; i++) cout << mat[i] << " ";
}
/*
5 4
5 7 3 1 1
2 6 11 2
*/