【2021牛客暑期多校训练营5】Jewels（建图，最小匹配权，KM乱搞）

J Jewels

题意：

• 给出n个点的位置x,y,z以及速度v，从第t=0秒开始打捞，打捞点i的代价为x^2+y^2+(z+t*v)^2，求打捞所有点的最小代价。

思路：

• 所有的宝石肯定都在 0~n-1 这 n 个时刻被挖掉，那么问题就变成一个最小权匹配了，一边是时刻，一边是宝石，边权就是在这个时刻挖这个宝石所消耗的体力值。
• 最小匹配权，可以用KM（即匈牙利算法），也可以跑费用流。但是神仙们直接乱搞，，反正就是暴力找增广路找到不能更优为止，这样的代码是最短的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, ans;
struct jew{LL z, v, id;}a[310];
LL f(LL t, jew x){t--;return t*t*x.v*x.v+2*t*x.v*x.z;}//边权
void g(int x){
	int t;
	for(int i = 1; i <= n; i++){ //找到当前宝石所匹配的时间
		if(a[i].id==x){t=i; break;}
	}
	for(int i = 1; i <= n; i++){//枚举所有的边
		if(f(i,a[i])+f(t,a[t])>f(t,a[i])+f(i,a[t])){//找增广路
			swap(a[i],a[t]);  //匹配宝石到时间更优的位置
			g(a[t].id); g(x); //暴力递归找增广路
		}
	}
}
int main(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		LL x, y, z, v;  cin>>x>>y>>z>>v;
		ans += x*x+y*y+z*z;
		a[i] = (jew){z,v,i};
	}
	for(int i = 1; i <= n; i++)g(i);
	for(int i = 1; i <= n; i++)ans+=f(i,a[i]);//累加答案
	cout<<ans<<"\n";
	return 0;
}



  

 

  
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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/119782459