2019 ICPC Asia Nanjing Regional J Spy (KM,最大权匹配)
题意:
A队有n个队,每个队赏金是p[i]
,能力值是a[i]
B队有2n个人现在要组成n个小队,每一个队从b[]
(长度为n)中取一个人,c[](
长度为n)中取一个人,组成小队,
组成的队伍的能力值是两个能力值之和。
现在B队中的每个小队,随机遇到A队中的一个小队进行比拼,如果B小队的能力值大于A小队
,就获胜并获得赏金,两个小队比拼之后就都out,不能再进行比拼。
问你期望得到的赏金n是多少?
解析:
就B队中b中的人作为二分图的x部,c中的人作为二分图y部,边x[i][j]
是如果将b[i]
和 c[j]
组成小队,所能得到的期望赏金n
然后用KM算法,做最大权匹配。
但是这里模板一定要选好。。。网上的一般的KM的模板都是
n
4
n^4
n4的
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
#define INFINITE 1 << 26
using namespace std;
typedef long long ll;
const int MAX = 450;
int n;
ll b[MAX],c[MAX];
ll d[MAX];
int sum[MAX];
typedef struct node
{
ll num;
int val;
}node;
node a[MAX];
int cost[MAX][MAX];
int lx[MAX],ly[MAX],match[MAX],slack[MAX];
int prevc[MAX];
bool vy[MAX];
void augment(int root)
{
fill(vy+1,vy+1+n,false);
fill(slack+1,slack+1+n,INF);
int py;
match[py=0] =root;
do{
vy[py]=true;
int x=match[py],yy;
int delta = INF;
for(int y=1;y<=n;y++)
{
if(!vy[y])
{
if(lx[x]+ly[y]-cost[x][y]<slack[y])
slack[y] = lx[x]+ly[y]-cost[x][y],prevc[y]=py;
if(slack[y]<delta) delta=slack[y],yy=y;
}
}
for(int y=0;y<=n;y++)
{
if(vy[y])
lx[match[y]] -= delta,ly[y] += delta;
else
slack[y] -= delta;
}
py=yy;
}while(match[py]!= -1);
do{
int pre = prevc[py];
match[py] = match[pre],py=pre;
}while(py);
}
int KM()
{
for(int i=1;i<=n;i++)
{
lx[i]=ly[i]=0;
match[i]=-1;
for(int j=1;j<=n;j++)
{
lx[i]=max(lx[i],cost[i][j]);
}
}
int answer =0;
for(int root = 1;root<=n;root++) augment(root);
for(int i=1;i<=n;i++) answer += lx[i],answer += ly[i];
return answer;
}
bool cmp(node a,node b)
{
return a.num<b.num;
}
int main()
{
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;
cost[i][j]=sum[last-1];
}
}
int ans=KM();
printf("%d\n",ans);
return 0;
}