2019 南京ICPC J. Spy KM算法

题目链接：https://nanti.jisuanke.com/t/42404
题目大意：
a[i]表示对手的每个队伍战斗力
p[i]表示打败对手后获得的声望
b[i]表示我方第一种人的战斗力
c[i]表示我方第二种人的战斗力

定义我方一组选手的战斗力为b[i]+c[j]，第一种选手与第二种选手某种顺序两两组队后，与对方进行pk，共有n!种pk顺序，你选择最佳的匹配方案，求能够获得最大期望声望×n。

思路：

我们假设b[i]和c[j]和组队，那么题目和对手然后一个打都是等可能的。能够获得的声望的期望为b[i]+c[j]>a[k]。的所有的p[k]的和/n。那么就可以把b[i]和c[j]建边直接跑KM。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N=405;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct KuhnMunkres {
    int n;//左右集合点数max(ln, rn)
    ll a[N][N];
    ll hl[N],hr[N],slk[N];//hl hr 左边集合的期望值，右边集合的期望值
    int fl[N],fr[N],vl[N],vr[N],pre[N],q[N],ql,qr;//fl fr,左右匹配对应的点 vl,vr用于bfs标记,
    int check(int i) {
        if(vl[i]=1,fl[i]!=-1)
            return vr[q[qr++]=fl[i]]=1;
        while(i!=-1)
            swap(i,fr[fl[i]=pre[i]]);
        return 0;
    }
    void bfs(int s) {
        memset(slk,0x3f,sizeof(slk));
        memset(vl,0,sizeof(vl));
        memset(vr,0,sizeof(vr));
        q[ql=0]=s;
        vr[s]=qr=1;
        for(ll d;;) {
            for(; ql<qr; ++ql)
                for(int i=0,j=q[ql]; i<n; ++i)
                    if(d=hl[i]+hr[j]-a[i][j],!vl[i]&&slk[i]>=d)
                        if(pre[i]=j,d)
                            slk[i]=d;
                        else if(!check(i))
                            return;
            d=INF;
            for(int i=0; i<n; ++i)
                if(!vl[i]&&d>slk[i])
                    d=slk[i];
            for(int i=0; i<n; ++i) {
                if(vl[i])
                    hl[i]+=d;
                else
                    slk[i]-=d;
                if(vr[i])
                    hr[i]-=d;
            }
            for(int i=0; i<n; ++i)
                if(!vl[i]&&!slk[i]&&!check(i))
                    return;
        }
    }
    ll ask(int nl, int nr) {
        n=max(nl,nr);
        memset(pre,-1,sizeof(pre));
        memset(fl,-1,sizeof(fl));
        memset(fr,-1,sizeof(fr));
        memset(hr,0,sizeof(hr));
        for(int i=0; i<n; ++i)
            hl[i]=*max_element(a[i],a[i]+n);
        for(int j=0; j<n; ++j)
            bfs(j);
        long long ans=0;
        for(int i=0; i<n; ++i)
            ans+=a[i][fl[i]];
        return ans;
    }
} km;

typedef struct node
{
    ll num;
    int val;
}node;

bool cmp(node a,node b)
{
    return a.num<b.num;
}

ll b[405],c[405];
ll d[405];
int sum[405];

node a[405];

int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].num);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].val);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&c[i]);
    }
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);

    sort(a+1,a+1+n,cmp);
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        sum[i] = sum[i - 1] + a[i].val;
        d[i]=a[i].num;
    }

    for(int i=1;i<=n;i++){
        int last=1;
        for(int j=1;j<=n;j++){
            ll val = b[i] + c[j];

            while(d[last] < val&&last<=n) last++;
            //if(!sum[last-1]) continue;

            km.a[i-1][j-1]=sum[last-1];
        }
    }

    printf("%d\n",km.ask(n, n));
    return 0;
}