Show the changes in ADT TreesWithCost TwC implementing the s

Show the changes in ADT TreesWithCost (TwC) implementing the steps of the algorithm (p.108). Start with seventeen TwC:
forall v do begin makeTree(v); addCost(v,huge) end

please help me with this question, thank you very much.

108 CHAPTER 8 find cost (v): Return the pair (w, x], where x is the minimum cost of a vertex on the tree path from v to findroot (v) and w is the last vertex on this path of cost add cost (v, x): Add x to the cost of every vertex on the tree path from v to findroot (v) link (v, w): Combine the two trees containing vertices v and w by adding the edge v must be a root) v, w cut (v): Divide the tree containing vertex v into two trees by deleting the edge out of v (v must be a nonroot) To find a blocking flow, we maintain for each vertex v a current edge [v, p(v)] on which it may be possible to increase the flow. These edges define a collection of trees. (Some vertices may not have a current edge.) The cost of a vertex v is cap (v, p(v)) f(v, p(v)) if v is not a tree root, huge if v is a tree root, where huge is a constant chosen larger than the sum of all the edge capacities. The following steps are a reformulation of Dinic\'s algorithm using the five tree operations. We find a blocking flow by first executing maketree (v) followed by addcost (v, huge) for all vertices, then going to advance and proceeding as directed Advance. Let v findroot (s). If there is no edge out of v, go to retreat Otherwise, let [v, wl be an edge out of v. Perform addcost (v, cap (v, w) huge) followed by link (v, w). Define p(v) to be w. If w t t, repeat advance; if t, go to augment Augment. Let [v, AJ find cost (s). Perform addcost A). Go to delete Delete. Perform cut (v) followed by addcost (v, huge). Define f(v, p(v)) cap (v, p(v)). Delete [v, p(v)] from the graph. Let [v, AJ findcost (s). If A 0, repeat delete, otherwise go to advance s halt. Otherwise, for every edge (u, v], delete [u, vj from the v Retreat. If graph and, if p(u) v, define f(u, v) 0; if p(u) v, perform cut (u), let Lu, AJ findcost (u), perform addcost (u, huge A), and define f(u, v) cap (u, v) 4. After deleting all edges [u, vj, go to advance Once the algorithm halts, we use cut, findcost, and addcost as in retreat to find the flow on every remaining edge THEOREM 8.10. The Sleator-Tarjan algorithm correctly finds a blocking flow in (m log n) time and a maximum ow in O(nm log n) time Proof. The correctness of the method is immediate. There are O(m) tree operations, giving a time bound of O(m log n) to find a blocking flow. The time bound for a maximum flow follows from Theorem 8.4 It is intriguing to contemplate the possibility of implementing the wave method using the data structure for cutting and linking trees, thereby obtaining an algorithm as fast as any known method on both sparse and dense graphs. We leaves this as an open problem; we conjecture that a time bound of o(m log (n2/m) for finding a blocking flow can be obtained in this way 8.4. Minimum cost flows. The idea of augmenting paths extends to a more general network flow problem. Let G be a network such that each edge [v, w] has a

Solution

// below program is used to create tree and add cost and to find the min cost

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
clrscr();

printf(\"\ Enter the no. of vertices\ \");
scanf(\"%d\",&n);
printf(\"\ Enter the cost adjacency matrix\ \");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
   scanf(\"%d\",&cost[i][j]);
   if(cost[i][j]==0)
    cost[i][j]=999;
}
}
printf(\"\ The edges of Minimum Cost Spanning Tree are\ \ \");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
   for(j=1;j<=n;j++)
   {
    if(cost[i][j]<min)
    {
     min=cost[i][j];
     a=u=i;
     b=v=j;
    }
   }
}
u=find(u);
v=find(v);
if(uni(u,v))
{
   printf(\"\ %d edge (%d,%d) =%d\ \",ne++,a,b,min);
   mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf(\"\ \\tMinimum cost = %d\ \",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}