Solved–Assignment XI –Solution

Description

1. You are resident of some hilly area. Your home is in low height compared to your office. Between your home and office there are number of roads and intersection of roads. Few roads are upwards/downwards (have some slope) and few roads are flat. Slope from locality X to locality Y is defined as |Y| – |X| (|X| indicates no of characters in X, positive slope indicates upward direction and negative slope is downward and 0 slope is flat road ). A locality named X will be attached with another locality named Y if

1. 1. Slope is 0

1. 2. Slope is +1/-1 and number of common character between X and Y is at least 1

1. 3. Slope is +2/-2 and number of common character between X and Y is at least 2

Distance between locality X and Y is defined as D_xy = . For example

X=Bhutan and Y=Nepal = (|N|-|B|) + (|h|-|e|) + (|u|-|p|) +(|t|-|a|)+(|l|-|a|)+(|n|-0) During morning when you go to office from home, you want to take a road which is strictly upward and shortest among such roads (consider only distance not slope). Write an efficient C program to find such road. You can randomly select your home and office from following localities and either find shortest path which is strictly upward from home to office or output that there is no such path exists.

Think carefully for efficiency of your program.

Example set of locality: Kullu, Manali, Kumaon, Darjeeling, Sikkim, Nainital,	Shimla,
Mussoorie, Almora, Chamba, Badrinath, Ranikhet, Gulmarg, Dalhousie, Lansdowne, Auli,
Gangtok, Along, Bomdila, Itanagar, Khonsa, Roing, Tawang, Ziro, Haflong, Hamren,
Jatinga, Maibang, Umrangso, Chirmiri, Mainpat, Baijnath, Barog, Chail,	Chitkul,

Churdhar, Dharamkot, Dharamshala, Haripurdhar, Jogindernagar, Kalpa, Kangra, Kasauli, Keylong, Khajjiar, Kiarighat, Kotla, Kufri, Kullu, Manali, Mashobra, Palampur, Rajgarh, Rewalsar, Sangla, Sarahan, Solan, Sundar, Triund

Upload Assignment11A.c

2. A graph is having n+2 vertices s,t, V₁, …V_n. There is an edge from V_x to V_y if 0<y-x<=3. Capacity of edge between V_x and V_y is (x+y). Node s is connected to node V_x where 1<=x<=n/4. Edge capacity of an edge between node s and V_x is x. There is an edge from V_x to node t where x>=3n/4 and x<=n. Consider s as source node and t as sink node in the graph, find the maximum possible flow from s to t with following

constraints:

1. Flow on an edge doesn’t exceed the given capacity of the edge.

2. Incoming flow is equal to outgoing flow for every vertex except s and t.

Upload Assignment11B.c