10984  Double NPhard
Moderator: Board moderators
10984  Double NPhard
Hi,
could someone give some test cases, i don't know what i'm doing wrong
thanks
could someone give some test cases, i don't know what i'm doing wrong
thanks

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Try this:
Correct output is: (edited to make it correct)
Case #1: Impossible
Case #2: Impossible
Code: Select all
2
6 4
1 2
1 3
5 4
5 6
6 5
1 2
1 3
1 5
5 4
5 6
Case #1: Impossible
Case #2: Impossible
Last edited by Adrian Kuegel on Sun Jan 22, 2006 6:11 pm, edited 2 times in total.
 Post removed by Observer 
Last edited by Observer on Sun Jan 22, 2006 5:58 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Hmm... probably the problemsetter has mistaken "maximum" as "maximal" then.. or maybe the test cases are just too simple ?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Edit: spoiler removed
Last edited by Adrian Kuegel on Mon Jan 23, 2006 12:25 am, edited 1 time in total.

 Learning poster
 Posts: 58
 Joined: Wed Dec 31, 2003 8:43 am
 Location: Dhaka, Bangladesh
 Contact:
thx for the hit. i already think that. But if the given graph is bipartite, then it's not sure that there is an answer. am i right ? Now tell me :Monsoon wrote:one hint: think what is when graph is bipartite and what is when it's not
1. if the total node is odd, then its "Impossible".
2. if the graph is bipartite and the given graph has an answer, then the output will be left part of the bipartite graph(i.e which part contais 1st node).
Am i right ?
Now tell me abt the minimum vertex cover portion. what's the way to handle this part ? A graph has no answer if not bipartite or it's minimum vetex set size != total node / 2. right ?
hope u get my problem.
pls help.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
You are right.
For minimum vertex cover, there exists an efficient algorithm if the graph is bipartite (which you can check first). Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution).
I guess, that the algorithm is also mentioned in some books about graph theory.
For minimum vertex cover, there exists an efficient algorithm if the graph is bipartite (which you can check first). Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution).
I guess, that the algorithm is also mentioned in some books about graph theory.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hmm. 1 Accepted and 34 Presentation Errors. Could it be that the judge has the wrong format? I'm (almost) sure my output is correctly formatted, but it's one of the 34.
No big deal, just want to mention it.
No big deal, just want to mention it.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.