Untitled
unknown
plain_text
2 years ago
7.4 kB
7
Indexable
Pha huy he thong dien
Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, VenG rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle.
Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất.
Hãy giúp anh VenG tìm hòn đảo này.
Input:
Dòng đầu tiên ghi số bộ test, không lớn hơn 100.
Mỗi bộ test được tổ chức theo khuôn dạng sau:
Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số hòn đảo.
Những dòng kế tiếp ghi lại ma trận biểu diễn hệ thong mạng lưới điện, trong đó 0 được hiểu là không có đường dây điện nối giữa điểm i và j, 1 được hiểu có đường dây điện trực tiếp giữa điểm i và điểm j (1<=i, j <= N).
Output
Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là hòn đảo bị phá hủy hệ thống điện thỏa mãn yêu cầu bài toán (nếu có nhiều đảo cùng thỏa mãn yêu cầu thì in ra đảo có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống điện, hãy in ra số 0.
Example
Input:
2
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
5
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0
Output:
3
0
5
10
0 1 1 1 0 0 0 0 0 0
1 0 1 0 0 0 1 0 0 0
1 1 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1
0 0 1 0 1 0 1 0 1 0
0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1 0 1
0 0 0 0 1 0 0 0 1 0
10
0 1 1 1 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0 0 0
1 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0 1 0
0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
15
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
1 1 0 1 0 1 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1 0 0 0 0 0
0 0 1 0 1 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 0 0 1
0 0 0 0 0 1 0 0 0 1 0 0 1 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
15
0 1 0 0 1 0 1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 1 0 0 1
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
15
0 1 0 0 1 0 1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 1 1 0 0 1
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 1 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 1
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int N;
int arr[100][100];
int vis[100][100];
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
ios::sync_with_stdio(false);
/*
The freopen function below opens input.txt in read only mode and
sets your standard input to work with the opened file.
When you test your code with the sample data, you can use the function
below to read in from the sample data file instead of the standard input.
So. you can uncomment the following line for your local test. But you
have to comment the following line when you submit for your scores.
*/
//freopen("input.txt", "r", stdin);
cin >> T;
/*
Read each test case from standard input.
*/
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
/////////////////////////////////////////////////////////////////////////////////////////////
/*
Please, implement your algorithm from this section.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
cin >> N;
for (int i=1;i<=N;i++) {
for (int j=1;j<=N;j++) {
cin >> arr[i][j];
}
}
// Print the answer to standard output(screen).
cout << "#" << test_case << " " << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
/*#include<iostream>
using namespace std;
int n, arr[100][100];
int visit[100], choose[100];
int Answer, temp;
void dfs(int x) {
visit[x] = 1;
for (int i = 0; i < n; i++) {
if (arr[x][i] == 1 && visit[i] == 0 && choose[i] == 0) dfs(i);
}
}
void solve(int x) {
for (int i = 0; i < n; i++) {
visit[i] = 0;
}
int cntt = 0;
for (int i = 0; i < n; i++) {
if (choose[i] == 0 && visit[i] == 0) {
cntt++;
dfs(i);
}
}
if (cntt == 1) return;
else if (cntt > temp) {
Answer = x + 1;
temp = cntt;
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = temp = 0;
cin >> n;
for (int i = 0; i < n; i++) {
choose[i] = visit[i] = 0;
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < n; i++) {
choose[i] = 1;
solve(i);
choose[i] = 0;
}
// Print the answer to standard output(screen).
cout << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}*/
/*#include<iostream>
int n,cnt,maxx,kq;
int map[100][100];
int save[100][100];
int vis[100];
int Qx[10000000];
int f,r;
using namespace std;
void push(int x){
f++;
Qx[f]=x;
}
int pop(){
r++;
return Qx[r];
}
void bfs(int n){
while (f!=r)
{
int x=pop();
vis[x]=1;
for(int i=0;i<n;i++){
if(save[x][i]==1&&vis[i]==0){
push(i);
}
}
}
cnt++;
}
void reset(int x){
for(int i=0;i<n;i++){
save[x][i]=map[x][i];
save[i][x]=map[i][x];
}
}
void set(int x){
for(int i=0;i<n;i++){
save[x][i]=0;
save[i][x]=0;
vis[i]=0;
}
}
int main(){
freopen("input.txt","r",stdin);
int T;
cin>>T;
for(int tc=1;tc<=T;tc++){
cin>>n;
for(int i=0;i<n;i++){
vis[i]=0;
for(int j=0;j<n;j++){
cin>>map[i][j];
save[i][j]=map[i][j];
}
}
f=r=-1;
maxx=0;
for(int i=0;i<n;i++){
cnt=0;
set(i);
vis[i]=1;
for(int j=0;j<n;j++){
if(vis[j]!=1){
push(j);
bfs(n);
if(cnt>maxx){
maxx=cnt;
kq=i;
}
f=r=-1;
}
}
reset(i);
}
if(maxx==1){
cout<<0<<endl;
}
else if(maxx>1)
{
cout<<kq+1<<endl;
}
}
return 0;
}*/
output
0
1
8
4
0
Editor is loading...