### 11095 - Tabriz City

Posted:

**Thu Sep 21, 2006 10:06 pm**Is it possible to solve this problem with graph coloring(two colors)???

I've used this and got WA!!

I've used this and got WA!!

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=33&t=12080

Page **1** of **1**

Posted: **Thu Sep 21, 2006 10:06 pm**

Is it possible to solve this problem with graph coloring(two colors)???

I've used this and got WA!!

I've used this and got WA!!

Posted: **Thu Sep 21, 2006 11:04 pm**

no it is not bicoloring!

It is vertex cover problem.

It is vertex cover problem.

Posted: **Fri Sep 22, 2006 6:38 am**

I think it would have been a bicoloring problem if the constraint was "If a junction has a tourist information centre, no adjacent junction can have another one" instead of "at least one of two junctions at the end of each street have a tourist information center"

Posted: **Fri Sep 22, 2006 4:08 pm**

try this input
the answer should be:
hope it helps

Code: Select all

```
1
15
20
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 3
6 3
6 4
8 9
9 10
10 11
11 12
11 13
12 13
13 14
8 14
8 11
9 14
```

Code: Select all

```
Case #1: 8
1 3 5 6 9 11 13 14
```

Posted: **Sat Sep 23, 2006 12:09 am**

Ok, AC now!!

Thanks

Thanks

Posted: **Sun Sep 24, 2006 2:15 am**

After i have read what vertex cover problem is, i agree this problem asks for the vertex cover, but how can you compute it?, specially when this is a NP problem whit n=30, do you have to make some kind of backtracking with pruning or something like that?, thanks in advance

Posted: **Tue Sep 26, 2006 1:36 pm**

Probably I haven't understood the problem clearly. Aren't we supposed to find the minimum number of information centers needed to form so that all the junctions have a center either at it or adjacent to it?

If so, for the graph posted by arsalan_mousavian 6 centers should be enough, I think. Don't 1 3 5 8 10 12 take care of all the junctions?

If so, for the graph posted by arsalan_mousavian 6 centers should be enough, I think. Don't 1 3 5 8 10 12 take care of all the junctions?

Posted: **Tue Sep 26, 2006 2:12 pm**

He wants to do this in a way that **at least one of two junctions at the end of each street** have a tourist information center

Posted: **Tue Sep 26, 2006 8:10 pm**

So it's the **streets** that must ensure that at least one end has a center. Yes, my previous assumption would have missed streets (4 6) and some more. Thank you Hisoka.

Posted: **Tue Sep 26, 2006 8:14 pm**

It is NP complete but the input size is quite small. BTW, if you read the graph as an array of edges the solution is kind of straight forward

Posted: **Fri Jun 01, 2007 6:44 pm**

What kind of optimization do you do in this problem? I have represented the graph using adjacency matrix; I am using bit field for marking... I am getting TLE, the code is basically a bruteforce search ... I select a node, mark all edges incident to it and then try other nodes, after returing from other nodes I simpy unmark the edges and try starting with other nodes... Can you share some of your tricks??? Thanks.

Posted: **Mon Jun 04, 2007 11:15 pm**

thanks to Vexorian... I got accepted easily by reading the graph as an array of edges...

the solution is obviously brute force search...

nymo, The only optimization that I did, was: whenever I decided not to take a vertex as an information centre, I marked all the adjacent vertices as taken. Hope it will help...

the solution is obviously brute force search...

nymo, The only optimization that I did, was: whenever I decided not to take a vertex as an information centre, I marked all the adjacent vertices as taken. Hope it will help...

Posted: **Tue Jun 05, 2007 10:35 am**

Thanks to MIB and Vexorian, I am now getting WAs... I try some test cases... they are okay. Can someone post some more test cases???

Thanks.

Thanks.

Posted: **Wed Jun 06, 2007 5:49 pm**

Thanks MIB. I 've got ACC

Posted: **Thu Jun 14, 2007 11:02 pm**

help me plz...

i use the approach of computing the nodes combination from small to large

in another word,try taking all possible 1 node and test ,then try taking 2 nodes combination,then 3...and more

but it become very slow after 8 nodes combination

i just got lots of TLE in online-judge...

plz tell me how should i design the brute force approach

will it be better if i use binary searching?

thx.

i use the approach of computing the nodes combination from small to large

in another word,try taking all possible 1 node and test ,then try taking 2 nodes combination,then 3...and more

but it become very slow after 8 nodes combination

i just got lots of TLE in online-judge...

plz tell me how should i design the brute force approach

will it be better if i use binary searching?

thx.