Link Sub: https://www.spoj.com/PTIT/problems/P145SUMH/
Người Gửi: Dương Lee
- Problem:
Khu vực nhà Tí bị mất điện dài ngày để khắc phục sự cố đường dây 500 kV. Các kỹ sư bảo rằng khu vực này có khi mất điện đến cả tháng trời. Vì vậy, các hộ dân ở đây đã sử dụng máy phát điện. Không phải hộ gia đình nào cũng có, vì vậy, họ đã kết nối với nhau để tạo thành hệ thống lưới điện riêng. Rõ ràng những gia đình nào ở càng xa nguồn phát thì điện sẽ càng yếu.
Tí muốn biết xem trong khu vực của mình, gia đình nào điện sẽ yếu nhất?
Độ yếu của điện tại hộ gia đình X được tính bằng 0 nếu hộ đó là hộ phát điện, nếu hộ X có kết nối điện với hộ Y mà hộ Y ở gần máy phát hơn, độ yếu tại hộ X = độ yếu tại hộ Y + 1. Nếu hộ X không có điện thì có độ yếu bằng vô cùng (infinity).
InputTí muốn biết xem trong khu vực của mình, gia đình nào điện sẽ yếu nhất?
Độ yếu của điện tại hộ gia đình X được tính bằng 0 nếu hộ đó là hộ phát điện, nếu hộ X có kết nối điện với hộ Y mà hộ Y ở gần máy phát hơn, độ yếu tại hộ X = độ yếu tại hộ Y + 1. Nếu hộ X không có điện thì có độ yếu bằng vô cùng (infinity).
Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số hộ gia đình, M là số hộ gia đình có máy phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).
Dòng tiếp theo gồm M số là ID các hộ gia đình có máy phát điện (ID đánh số từ 0 tới N-1).
H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết hộ gia đình u có kết nối với hộ gia đình.
Dòng tiếp theo gồm M số là ID các hộ gia đình có máy phát điện (ID đánh số từ 0 tới N-1).
H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết hộ gia đình u có kết nối với hộ gia đình.
Output
Example:
In ra hộ gia đình có độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra hộ có ID nhỏ nhất.
Input
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
Output:
1
Input
6 2 3
5 2
0 5
0 1
3 4
Output:
3
- Solution:
Input
6 2 3
5 2
0 5
0 1
3 4
Output:
3
Ban đầu coi tất cả các hộ gia đình có độ yếu của điện là: infinity (>1000 - vì chỉ có tối đa 1000 hộ)
Bài này sau khi setup hệ thống đường dây điện (chính là biểu diễn các hộ gia đình theo danh sách kề - biểu diễn đồ thị)
Chỉ cần BFS từ các điểm phát phát đếm bước đi ngắn nhất đến các căn hộ khác. Điện của max của mỗi hộ = min(tất cả trường hợp yếu điện từ nguồn phát đến hộ đó)
Cuối cùng độ yếu điện lớn nhất chính là max(điện tất cả các hộ).
Bài này sau khi setup hệ thống đường dây điện (chính là biểu diễn các hộ gia đình theo danh sách kề - biểu diễn đồ thị)
Chỉ cần BFS từ các điểm phát phát đếm bước đi ngắn nhất đến các căn hộ khác. Điện của max của mỗi hộ = min(tất cả trường hợp yếu điện từ nguồn phát đến hộ đó)
Cuối cùng độ yếu điện lớn nhất chính là max(điện tất cả các hộ).
- Code:
C++:
https://ideone.com/C1yMXV
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, h;
vector< int > generator;
vector< int > line[1003];
void Read()
{
cin>>n>>m>>h;
for (int i=0; i<m; i++)
{
int tmp;
cin>>tmp;
generator.push_back(tmp);
}
for (int i=0; i<h; i++)
{
int a, b;
cin>>a>>b;
line[a].push_back(b);
line[b].push_back(a);
}
}
int weak[1003];
void Init()
{
for (int i=0; i<n; i++)
{
weak[i] = 1003;
}
}
int check[1003];
int trans[1003];
void Reset()
{
for (int i=0; i<n; i++)
{
check[i] = 0;
trans[i] = -1;
}
}
void BFS(int u)
{
check[u] = 1;
queue<int> q;
q.push(u);
trans[u] = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
for (int i=0; i<line[u].size(); i++)
{
int v = line[u][i];
if (check[v] == 0)
{
q.push(v);
check[v] = 1;
trans[v] = trans[u] + 1;
}
}
}
}
void CheckWeak()
{
for (int i=0; i<n; i++)
{
if (trans[i]!=-1)
{
if (trans[i]<weak[i])
{
weak[i] = trans[i];
}
}
}
}
void OUT()
{
int p = 0;
for (int i=1; i<n; i++)
{
if (weak[i] > weak[p])
{
p = i;
}
}
cout<<p;
}
void Test()
{
for (int i=0; i<n; i++)
{
cout<<check[i]<<" ";
}
cout<<endl;
for (int i=0; i<n; i++)
{
cout<<trans[i]<<" ";
}
cout<<endl;
for (int i=0; i<n; i++)
{
cout<<weak[i]<<" ";
}
}
int main()
{
// freopen("input.txt", "r", stdin);
Read();
Init();
for (int i=0; i<m; i++)
{
Reset();
BFS(generator[i]);
CheckWeak();
}
OUT();
// test();
return 0;
}JAVA:
...Python:
...