1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 650
struct node {
LL x,y,z,v;
} dat[MAXN];
int n;
namespace KM {
LL w[MAXN][MAXN],slack[MAXN],lx[MAXN],ly[MAXN];
bool vis2[MAXN];
int pre[MAXN],match[MAXN];
void bfs(int p) {
memset(vis2,0,sizeof(vis2));
memset(pre,0,sizeof(pre));
memset(slack,63,sizeof(slack));
int x,y=0,yy=0;
LL d;
match[0]=p;
do {
x=match[y];
vis2[y]=true;
d=0x3f3f3f3f3f3f3f3f;
for(int i=1; i<=n; i++) {
if(vis2[i])continue;
if(slack[i] > lx[x]+ly[i]-w[x][i]) {
slack[i]=lx[x]+ly[i]-w[x][i];
pre[i]=y;
}
if(slack[i] < d) {
d=slack[i];
yy=i;
}
}
for(int i=0; i<=n; i++) {
if(vis2[i])
lx[match[i]]-=d,ly[i]+=d;
else
slack[i]-=d;
}
y=yy;
} while(match[y]);
while(y) {
match[y]=match[pre[y]];
y=pre[y];
}
}
LL Max_Match() {
LL ret=0;
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(match,0,sizeof(match));
for(int i=1; i<=n; i++)bfs(i);
for(int i=1; i<=n; i++)ret+=w[match[i]][i];
return ret;
}
}
int main() {
LL ans=0;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%lld%lld%lld%lld",&dat[i].x,&dat[i].y,&dat[i].z,&dat[i].v);
ans+=dat[i].x*dat[i].x+dat[i].y*dat[i].y+dat[i].z*dat[i].z;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
KM::w[i][j]=-(1ll*2*(i-1)*dat[j].z*dat[j].v + 1ll*(i-1)*1ll*(i-1)*dat[j].v*dat[j].v);
ans+=-KM::Max_Match();
printf("%lld\n",ans);
return 0;
}
|