[网络协议]湖南大学第十六届程序设计竞赛（重现赛）J Yuki with playf（二分图最大权匹配）

题目链接：传送门
资料链接：洛谷二分图题目题解
思路：


代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,ll> P;
const int N = 5e2 + 50;
const int M = 1e6 + 50;
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int nx, ny;//两边的点数
ll cap[N][N];//二分图描述
ll linkery[N], lx[N], ly[N];//y 中各点匹配状态，x,y 中的点标号
ll udp[N];
bool visx[N], visy[N];
ll vis[M];
int pre[N];
ll delta;
ll n,m;
ll c[N],p[N];
void init() {
    vis[1] = inf;
    for (ll i = 2;i <= 1000;i++) {
        if (!vis[i]) {
            vis[i] = i;
            for (ll j = i * i;j <= 1000000;j += i) {
                if (!vis[j])vis[j] = i;
            }
        }
    }
    for (int i = 2;i <= 1000000;i++) {
        if (!vis[i])vis[i] = i;
    }
}
ll cla(ll a, ll b) {
    if (a * b <= 2)return 0;
    if (a * b % 3 == 0)return a * b / 3;
    if (a * b % 4 == 0)return a * b / 4;
    ll temp = a * b;
    if (temp <= 1e6) {
        if (temp % 2 == 0)return temp / vis[temp / 2];
        return temp / vis[temp];
    }
    temp = a * b;
    while(vis[a] == 2)a /= 2;
    while(vis[b] == 2)b /= 2;

    return temp / min(vis[a], vis[b]);
}
void bfs(ll k){
    int x,y=0,yy=0;
    linkery[y]=(ll)k;
    memset(udp,1e13,sizeof(udp));
    memset(pre,0,sizeof(pre));
    while(1){
        x = linkery[y];
        delta=1e13;
        visy[y]=1;
        for(int i=1;i<=ny;i++){
            if(!visy[i]){
                if(udp[i]>lx[x]+ly[i]-cap[x][i]){
                    udp[i]=lx[x]+ly[i]-cap[x][i];
                    pre[i]=y;
                }
                if(udp[i]<delta)delta=udp[i],yy=i;
            }
        }
        for(int i=0;i<=ny;i++){
            if(visy[i]){
                lx[linkery[i]]-=delta;
                ly[i]+=delta;
            }else{
                udp[i]-=delta;//维持正确的结果，都有可能是相等边，所以-=delta;
            }
        }
        y=yy;
        if(linkery[y]==-1)break;
    }
    while(y){
        linkery[y]=linkery[pre[y]];
        y=pre[y];
    }

}

ll km(){
    memset(linkery,-1,sizeof(linkery));
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    for(int i=1;i<=ny;i++){
        memset(visy,0,sizeof(visy));
        bfs(i);
    }
    ll res=0;
    for(int i=1;i<=ny;i++){
        if(linkery[i]!=-1)res+=cap[linkery[i]][i];
    }
    return res;
}
int main(){
    init();
    scanf("%lld%lld", &n, &m);
    for(int i=1;i<=n;i++){
        scanf("%lld", &c[i]);
    }
    for(int j=1;j<=m;j++){
        scanf("%lld", &p[j]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cap[i][j]=(ll)cla(c[i],p[j]);
        }
    }
    ny=nx=max(n,m);
    printf("%lld",km());
    return 0;
}

代码解释：

            if(visy[i]){
                lx[linkery[i]]-=delta;
                ly[i]+=delta;
            }else{
                udp[i]-=delta;//维持正确的结果，都有可能是相等边，所以-=delta;
            }
            因为计算udp[i]=lx[x]+ly[i]-cap[x][i];，lx[x]是经过linkery[i]-=delta,所以要加上个delta,通过udp数组来进行