SPOJ.com - Problem BCACM11E

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCACM11E - Phương án bắn pháo

Một hệ thống phòng thủ của địch gồm N điểm (N<=100), giữa các điểm bất kỳ của hệ thống đều có thể đi lại trực tiếp hoặc gián tiếp với nhau thông qua hệ thống các đường hầm. Bài toán được đặt ra là cho trước một hệ thống phòng thủ, hãy giúp bộ đội sử dụng đúng 1 quả pháo bắn vào một trong N điểm sao cho hệ thống bị chia cắt thành nhiều mảnh nhất.

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ố điểm của hệ thống phòng thủ.
Những dòng kế tiếp ghi lại ma trận G = (g_ij) biểu diễn hệ thống phòng thủ, trong đó g_ij=0 được hiểu là không có đường hầm trực tiếp nối giữa điểm i và j, g_ij =1 được hiểu có đường hầm nối 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à đỉnh bị phá hủy thỏa mãn yêu cầu bài toán (nếu có nhiều đỉnh cùng thỏa mãn yêu cầu thì in ra đỉnh có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống, hãy in ra số 0.

Example

Input:

0 1 1 0 0

1 0 1 0 0

1 1 0 1 1

0 0 1 0 0

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

ID	RESULT	TIME

code...

Submit solution!

Được gửi lên bởi:	adm
Ngày:	2011-10-20
Thời gian chạy:	0.203s-1.018s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Nguồn bài:	ACM PTIT 2011

hide comments



2021-07-28 10:42:54 Trâu cũng AC
2017-08-20 20:09:18 Con Bò Huyền Thoại http://kienthuc24h.com/bcacm11e-spoj-ptit-phuong-an-ban-phao/
2017-07-23 08:07:19 BCACM11E: https://e16cn-ptit.blogspot.com/2017/12/bcacm11e-phuong-an-ban-phao.html Last edit: 2017-12-09 22:00:27
2016-09-23 16:42:56 1 đấm AC
2016-08-10 09:29:41 zon Tưởng chỉ cần đếm số thành phần khi bỏ đỉnh xét là xong chứ
2015-03-26 12:23:33 Con Bò Huyền Thoại Last edit: 2017-08-20 20:09:25
2014-08-08 11:02:00 Con Bò Huyền Thoại khớp + đếm thành phần liên thông :D
2014-02-26 16:11:25 Vani mới tìm được bài giải , có thể tham khảo tại: http://thuattoan.info/?p=324

Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

BCACM11E - Phương án bắn pháo

Example