首页 > 其他分享 >P1522 [USACO2.4] 牛的旅行 Cow Tours

P1522 [USACO2.4] 牛的旅行 Cow Tours

时间:2024-08-08 11:28:47浏览次数:11  
标签:return Cow int fa second Tours USACO2.4 first dis

思路

对于每个连通块求出任意两点距离的最大值 \(max[u]\),然后再 \(O(n^2)\) 枚举任意两个连通块连接起来,答案就是两个连通块的最大值 \(max\) 加上中间连接的边的长度。

代码

#include <bits/stdc++.h>

using namespace std;
using PDD = pair<double, double>;

const int N = 160;

int fa[N];

int find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx == fy) return;
	fa[fx] = fy;
}

int n;
PDD a[N];
double dis[N][N], maxd[N];
double zjd[N];

double gdis(PDD a, PDD b) {
	return sqrt(((a.first - b.first) * (a.first - b.first)) + ((a.second - b.second) * (a.second - b.second)));
}

int main() {	
	cin >> n;
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char c;
			cin >> c;
			if (c == '1') {
				dis[i][j] = gdis(a[i], a[j]);
				merge(i, j);
			}
			else dis[i][j] = 1e18;
		}
	}
	
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dis[i][j] > dis[i][k] + dis[k][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int fx = find(i), fy = find(j);
			if (fx == fy && i != j) {
				zjd[fx] = max(dis[i][j], zjd[fx]);
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j && find(i) == find(j) && dis[i][j] < 1e17) maxd[i] = max(maxd[i], dis[i][j]);
		}
	}
	
	double ans = 1e18;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (find(i) == find(j)) continue;
			ans = min(ans, max(max(zjd[find(i)], zjd[find(j)]), maxd[i] + maxd[j] + gdis(a[i], a[j])));
		}
	}
	printf("%.6lf", ans);
	return 0;
}

标签:return,Cow,int,fa,second,Tours,USACO2.4,first,dis
From: https://www.cnblogs.com/Yuan-Jiawei/p/18348604

相关文章

  • D37 2-SAT P3007 [USACO11JAN] The Continental Cowngress G
    视频链接:D372-SATP3007[USACO11JAN]TheContinentalCowngressG_哔哩哔哩_bilibili  P3007[USACO11JAN]TheContinentalCowngressG-洛谷|计算机科学教育新生态(luogu.com.cn)//O(n*n)#include<iostream>#include<cstring>#include<algorithm>usin......
  • K11505 The Lost cow[USACO-2017-USOpen-B]
    题目描述FarmerJohn最珍贵的奶牛Bessie丢了,他需要把它找回来。幸运的是,农场里只有一条长长的直路,他知道Bessie肯定在这条路上的某个地方。如果我们把这条路看成数轴,假设FarmerJohn所在位置是x,Bessie所在的位置是y(对于John是未知的),如果FarmerJohn知道Bessie的位置,那么他就......
  • 洛谷题单指南-前缀和差分与离散化-P3029 [USACO11NOV] Cow Lineup S
    原题链接:https://www.luogu.com.cn/problem/P3029题意解读:不同的坐标位置有不同种类的牛,要计算一个最小的区间,包括所有种类的牛。解题思路:由于坐标位置不连续,并且数值范围较大,因此需要离散化处理,将坐标处理成1~n连续分布由于种类编号数值范围也比较大,也需要离散化处理,去重后的......
  • [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包
    凸包,顾名思义,就是凸多边形包围,具体定义见OI-wiki(既是周长最小也是面积最小)有Graham算法和Andrew算法,后者精度更高常数更小(因为不涉及求角度)Andrew算法:1.将点排序(横坐标为第一关键字,纵坐标为第二关键字)2.从左到右维护上半部分,再从右到左维护下半部分。具体见OI-wiki。最后说的......
  • POJ3278 Catch That Cow
    CatchThatCowTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 222142 Accepted: 67092DescriptionFarmerJohnhasbeeninformedofthelocationofafugitivecowandwantstocatchherimmediately.Hestartsatapoint N (0......
  • 题解:P10450 [USACO03MAR] Best Cow Fences G
    题目链接O(n^3)做法直接暴力枚举长度、起点,再全部跑一边求平均数。附上我丑陋的代码和提交记录,这个代码可以得42分。#include<bits/stdc++.h>usingnamespacestd;constintNR=1e5+5;longlongn,l,a[NR],sum,ave;intmain(){ cin>>n>>l; for(inti......
  • P10280 [USACO24OPEN] Cowreography G 题解
    Description奶牛们组了一支舞蹈队,FarmerJohn是她们的编舞!舞蹈队最新而最精彩的舞蹈有\(N\)头奶牛(\(2\leN\le10^6\))排成一行。舞蹈中的每次动作都涉及两头奶牛,至多相距\(K\)个位置(\(1\leK<N\)),优雅地跳起并降落在对方的位置上。队伍中有两种奶牛——更赛牛(Guernsey)和荷......
  • P3089 [USACO13NOV] Pogo-Cow S
    原题链接题解暴力dp:遍历\(i,j,k\),\(dp[i][j]=\max(dp[j][k])+v_i\)其中\(x_i-x_j\geqx_j-x_k\)优化:对于\(j\)来说,随着\(i\)越大,\(k\)可以越小,因此省去了遍历一层\(k\),而是维护每个点的\(k\),(反正求的是最大值)细节1.有两个方向2.任意起点code#include<bit......
  • mailcow邮件服务器的安全防护措施有哪些?
    mailcow邮件服务器如何搭建?邮件服务器的优势特点?mailcow邮件服务器是一款功能强大的开源电子邮件服务器套件,旨在为用户提供高效、安全的邮件服务。为了确保邮件服务器的安全,mailcow邮件服务器采取了一系列的安全防护措施,AokSend将详细探讨这些措施。mailcow邮件服务器:访问控......
  • qcow2恢复案例
    确认文件和进程信息:使用lsof命令确认虚拟机进程正在使用已删除的qcow2文件,并记录文件描述符和虚拟机进程ID(例如3914和11u)。sudolsof|grepdeleted复制文件内容:使用文件描述符路径复制已删除的qcow2文件到一个新的目标位置。例如,假设文件描述符路径为/proc/3914/fd/11,将文件......