hint in a question

The publicity team for Technozion is in full swing. Like every year, this time too, the team is planning to visit N different colleges in India. This publicity campaign shall involve the members of the team giving presentations about Technozion.

For the publicity trip, the team has decided to come up with two different types of presentations(Presentation A and Presentation B) to be delivered at the colleges they visit.

Your job is to help them carry on this task in a more organized manner.

You shall be given with the total number of students (population) studying in each college, as well as the highways between the colleges. You need to help the team plan a trip such that no two colleges which are connected directly by a highway are given the same presentation and such that the difference between the number of students who attend the Presentation A and those who attend the Presentation B is minimal .

Your final task is to help out our team by providing them with the absolute minimal difference between the number of students who will attend Presentation A and who will attend Presentation B ,so that all the conditions above are satisfied.

Input Format :

First line of the input contains a single integer M, the number of bi-directional Highways.
Then M lines describing bi-directional Highways follow, each of them contains two integers (u, v) representing a
Highway connecting college u and college v.
After this Follow a single line containg an Integer N (Numbered 0 to N-1) indicating the total Number of colleges.
Then Follows N Lines ,each containing a single integer indicating the total number of student in ith college.
Output Format:
For each test case, output a single integer - the absolute minimal difference between the number of students who will attend
Presentation A and who will attend Presentation B,as described above.

Please give me hint in this question how to proceed. :)

[np complete]

This is kind of travelling salesman problem. Anyways by your question, I could'nt understand where to start. Lets suppose you start with a college 'x'. Then for each college joined to 'x' by highway, calculate the difference between students, traverse the minimum one. Then apply th algorithm again.

But first you must figure out a data structure for this problem. Also read travelling salesman problem and some basic notes on graph theory, might help you figuring out the shortest path.

Nice question by the way :-)

any other hint ?

[np complete]

You may use Dijkstra's algorithm.
Wiki page.

I thin you are interpreting the question wrongly. only directly linked nodes must not have same prsentation. So how this algo is adjustng this thing in between ? can u again read the question again ?

[WaltP]

The publicity team for Technozion is in full swing. Like every year, this time too, the team is planning to visit N different colleges in India. This publicity campaign shall involve the members of the team giving presentations...

How about presentations on

"The Benefits of Using 25-year-old technology (TurboC) and Handcuffing the Students to (equivalently) Bronze Age Technology".

"How the Word 'Question' Becomes Twisted into the Word 'Doubt'"

"How to Make Yourself Understood When They Call Your American Tech Help Desk"

But I kid... ;o)

@waltP sir, it's ok again that u are kidding. But seriously, i want to explain you one thing, when you try these types of things on anybody's thread or mine then i have seen that nobody ever replies again. i don't know why. I am not arguing with u. but these things look nice SOMETIMES but not ALWAYS which you do. anyways, thanks for ur valuable replies.if you don't know thw answer and want to mock , then do it when thread is solved or come close to completion. I know THAT THIS THREAD IS NOW DESTROYED BECAUSE no body will reply now. no deceptikon, no waltP(not this one waltP as you behave multiple personatilies ), no ancient Dragon now in this thread. thanks to you only.

@deceptikon Do you really think WaltP is adding something in my posts ? Do you really think so ? Tell me this thing. Do u really think this ? the post he has made is adding something ? After his posts, see nobody is replying in this post, not even npcomplete who was helping me a little bit.

[deceptikon]

After his posts, see nobody is replying in this post, not even npcomplete who was helping me a little bit.

After np_complete's posts, you appear to have done nothing except ask for more hints. Why should others try to help you when you clearly ignored the one who did? It has nothing to do with someone else "destroying" your thread, you've accomplished that yourself by making helpers feel unwelcome.

Excessive ass kissing is creepy. Outright hostility is repulsive. Maybe you should try somewhere in the middle.

Excessive ### kissing is creepy. Outright hostility is repulsive. Maybe you should try somewhere in the middle. what is meant by this ?

[deceptikon]

Excessive ass kissing is what you've been doing with me. Calling me a genius, always acting like only my responses are worth anything to you, and in general fawning over me. I know you're just trying to show respect, but it makes me uncomfortable.

Outright hostility is what you've been doing with WaltP. He may be gruff, but he's done nothing to hurt you or your threads, despite what you may think. If you don't like him or his posts, ignore him. That's what mature people will do on a public forum when no rules are broken. If he breaks a rule, report the post with the Flag Bad Post button.

I'm suggesting that you learn how to simply ignore insults, imagined or not. Try to be polite, but you don't have to treat people who help you like gods; doing so could easily turn them off from helping you in the future because it's often perceived as creepy.

only one thing i can say while treating you as my teacher and showing universal and ultimate respect to you and your help :- "Sorry, for being so calm , unprofessional , ### kissy, respectful, calling you genius, sharing every thing with you and excitingly waiting for your replies. that's all. " till now, you were james sir for me and now onwards you are deceptikon for me. thanks for making me aware of these things.

SEcondly, WaltP is WaltP. will wish he will not reply on my posts. If any admin or anybody has problem with me(as i am nothing in front of them), then they can ban me any time. thnaks.

[deceptikon]

If any admin or anybody has problem with me(as i am nothing in front of them), then they can ban me any time. thnaks.

That's not how it works. If you break the rules enough to accumulate too many infraction points, you'll be banned automatically by the system. Otherwise, you'll not be banned...ever.

okay deceptikon. that was a good to know, otherwise i was thinking something else. thanks to you. Any other response will also be appreciated.