|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Help | Liu Qi | 1557. Network Attack | 23 май 2021 01:19 | 2 | Help Liu Qi 9 янв 2010 06:04 I always get a wrong answer on test 11，who can help me？ Re: Help Maydell Anton 23 май 2021 01:19 This small test helped me to move from WA on test 11 to AC.
3 4
3 2
1 3
2 1
1 2
ans: 1 | | Data | xuesu | 1557. Network Attack | 10 июл 2015 13:42 | 2 | Data xuesu 17 фев 2015 20:53 18 32
5 11
9 2
17 16
16 7
2 12
13 2
16 4
5 17
4 13
14 17
17 17
11 3
11 15
9 3
13 10
3 8
16 13
7 16
10 11
11 13
14 8
7 4
16 10
1 11
15 2
2 12
13 12
1 14
3 14
8 6
14 1
18 1
ans:65 Re: Data zhengjinke2123 10 июл 2015 13:42 5 7
4 5
1 2
2 3
3 4
3 4
3 4
1 5
ans : 6 | | Get MLE using java. And C++ got Accept! | LuQi | 1557. Network Attack | 18 окт 2013 20:34 | 1 | | | 1557. Network attack | mahbubul | 1557. Network Attack | 5 фев 2012 15:41 | 5 | I am getting WA in second case i dont know why.
my idea is: first find out the number of articulation bridge in the graph say n. then ans1 = nC2 + n*(E-n).
then, we need to merge all the multiple edge and again find out all the biconnected component. there after:
ans2 = number of nodes having degree 2 within its own component.
ans3 = number of nodes having degree (multiple edge) 2 with one another component.
then ans = asn1 + ans2 + ans3/2.
I cant understand where does my code fail? can any one help? Try this test :
6 10
1 2
1 2
2 3
1 3
4 5
5 6
4 6
4 6
2 4
3 5
The answer is 1 : (2,4) and (3,5)
Edited by author 06.10.2007 02:10 We must use standard theory as possible.
I think problems divided to two parts:
1. Find all bridges- well known,O(n+m) algorithms;
2. Find all 2-cuts - I don't know algoriths and
best complexity.
I think It is must be something as 3-connected blocs structure.
Edited by author 07.11.2007 12:40 i make a perfect algorithm of O(m+n)to find 2-cuts I've solved this problem, but i'm intrested in a different ways to compute 2-cuts. Could you send me your code?
marqueewinq@gmail.com | | Wa 4 | xkszltl | 1557. Network Attack | 19 июн 2010 09:16 | 1 | Wa 4 xkszltl 19 июн 2010 09:16 I'm Wa 4，Who can help me?!!! | | new tests | Milanin (TNU) | 1557. Network Attack | 15 фев 2010 15:38 | 2 | My old accepted program does not pass some tests. Maybe it concerns only my solution, however it would be quite good to add these tests. | | Unclear problem statement | Denis Koshman | 1557. Network Attack | 15 июл 2008 03:11 | 1 | "Each hacker can destroy exactly one channel"
What does it mean: "can" by "exactly"? Usually it is said "not more than one".
The question is - can a hacker do nothing? This is especially important for cases with M=0 and M=1. |
|
|
|
