【图论 BFS染色 并集查找 】P3663 [USACO17FEB] Why Did the Cow Cross the Road III S|普及+
本文涉及知识点
C++图论
C++并集查找 预计2025年5月29号 7:00发布
C++BFS算法
P3663 [USACO17FEB] Why Did the Cow Cross the Road III S
题目描述
奶牛为什么要过马路？其中一个原因是 Farmer John 的农场有很多道路，使得他的奶牛在四处走动时不可避免地要穿过许多道路。
FJ 的农场被安排成一个 N × N N \times N N×N 的方形网格田地（ 2 ≤ N ≤ 100 2 \leq N \leq 100 2≤N≤100），某些相邻的田地（例如南北向或东西向）被道路分隔，整个网格的外部有一圈高高的围栏，防止奶牛离开农场。奶牛可以从任何田地自由移动到相邻的田地（北、东、南或西），尽管它们除非绝对必要，否则不愿意穿过道路。
农场上有 K K K 头奶牛（ 1 ≤ K ≤ 100 , K ≤ N 2 1 \leq K \leq 100, K \leq N^2 1≤K≤100,K≤N2），每头奶牛位于不同的田地。如果一头奶牛要拜访另一头奶牛时必须至少穿过一条道路，那么这对奶牛被称为“远距离”对。请帮助 FJ 计算远距离奶牛对的数量。
输入格式
输入的第一行包含 N N N、 K K K 和 R R R。接下来的 R R R 行描述了 R R R 条存在于相邻田地之间的道路。每行的格式为 r r r c c c r ′ r' r′ c ′ c' c′（范围为 1 … N 1 \ldots N 1…N 的整数），表示位于（行 r r r，列 c c c）的田地与相邻的（行 r ′ r' r′，列 c ′ c' c′）的田地之间有一条道路。最后的 K K K 行表示 K K K 头奶牛的位置，每行用行和列指定。
输出格式
输出远距离奶牛对的数量。
输入输出样例 #1
输入 #1
3 3 3 2 2 2 3 3 3 3 2 3 3 2 3 3 3 2 2 2 3
输出 #1
2
并集查找
本题 ⟺ \iff ⟺ 4连接的单格连通，除非2个单格间有路。求在不连通区域的奶牛对数量。
编码（二维转一维）Mask(r,c) {return rC+c;}
not[mask]记录不连通的4连接单格，如果mask和mask1不连通，则not[mask].push_back(mask1)
not[mask1].push_back(mask)
neiBo[mask]记录mask的临接点，4连接除not外的数据。
利用nieBo并集查找各节点所属联通区域，计算各连通区域奶牛数量。
枚举各联通区域奶牛数量x
ans +=x(K-x)
最终结果ans/2。
注意：也可以用BFS染色法求联通区域。
代码
核心代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template
std::istream& operator >> (std::istream& in, pair& pr) {
in >> pr.first >> pr.second;
return in;
}
template
std::istream& operator >> (std::istream& in, tuple& t) {
in >> get(t) >> get(t) >> get(t);
return in;
}
template
std::istream& operator >> (std::istream& in, tuple& t) {
in >> get(t) >> get(t) >> get(t) >> get(t);
return in;
}
template
vector Read() {
int n;
scanf("%d", &n);
vector ret(n);
for (int i = 0; i > ret[i];
}
return ret;
}
template
vector Read(int n) {
vector ret(n);
for (int i = 0; i > ret[i];
}
return ret;
}
template
class COutBuff
{
public:
COutBuff() {
m_p = puffer;
}
template
void write(T x) {
int num[28], sp = 0;
if (x N - 100) {
ToFile();
}
}
char puffer[N], * m_p;
};
template
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff& operator>>(char& ch) {
FileToBuf();
ch = *S++;
return *this;
}
inline CInBuff& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x (long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x (pair& val) {
*this >> val.first >> val.second;
return *this;
}
template
inline CInBuff& operator>>(tuple& val) {
*this >> get(val) >> get(val) >> get(val);
return *this;
}
template
inline CInBuff& operator>>(tuple& val) {
*this >> get(val) >> get(val) >> get(val) >> get(val);
return *this;
}
template
inline CInBuff& operator>>(vector& val) {
int n;
*this >> n;
val.resize(n);
for (int i = 0; i > val[i];
}
return *this;
}
template
vector Read(int n) {
vector ret(n);
for (int i = 0; i > ret[i];
}
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos - (S - buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for(int i = 0 ;i > N >> K >>R ;
auto broad = ib.Read(R);
auto pos = ib.Read(K);
#ifdef _DEBUG
printf("N=%d,", N);
Out(broad, ",broad=");
Out(pos, ",pos=");
/*Out(edge, "edge=");
Out(que, "que=");*/
#endif // DEBUG
auto res = Solution().Ans(N,broad,pos);
cout
N = 3, broad = { {2,2,2,3},{3,3,3,2},{3,3,2,3} }, pos = { {3,3},{2,2},{2,3} };
auto res = Solution().Ans(N, broad, pos);
AssertEx(2, res);
}
