Abhishek Chavan | 122B1B047
Assignment-6
package com;
import java.util.*;
class Node{
Node parent;
int pathCost,cost,studid,clubid;
boolean assigned[];
public Node(int N){ assigned=new boolean[N]; }
}
public class assn {
static int N;
static Node newnode(int x,int y,boolean asn[],Node par) {
Node node=new Node(N);
System.arraycopy(asn, 0, node.assigned, 0, N);
if(y!=-1) node.assigned[y]=true;
node.parent=par;
node.studid=x;
node.clubid=y;
return node;
}
static int calcost(int costmat[][],int x,int y,boolean asn[]) {
int cost=0;
boolean avail[]=new boolean[N];
Arrays.fill(avail,true);
for(int i=x+1;i<N;i++){
int min=Integer.MAX_VALUE, minIndex=-1;
for(int j=0;j<N;j++){
if(!asn[j] && avail[j] && costmat[i][j]<min){
minIndex=j;
min=costmat[i][j];
}
}
cost+=min;
avail[minIndex]=false;
}
return cost;
}
static void prints(Node min){
if(min.parent==null) return;
prints(min.parent);
System.out.println("Assign Student "+(char)(min.studid+'A')+" to Club "+min.clubid);
}
static int findmin(int costmat[][]) {
PriorityQueue<Node>pq=new PriorityQueue<>(Comparator.comparingInt(node-
>node.cost));
boolean assigned[]=new boolean[N];
Abhishek Chavan | 122B1B047
Node root=newnode(-1,-1,assigned, null);
root.pathCost=root.cost=0;
root.studid=-1;
pq.add(root);
while (!pq.isEmpty()){
Node min=pq.poll();
int i=min.studid+1;
if (i==N){
prints(min);
return min.cost;
}
for(int j=0;j<N;j++){
if(!min.assigned[j]){
Node child=newnode(i,j,min.assigned,min);
child.pathCost=min.pathCost+costmat[i][j];
child.cost=child.pathCost+calcost(costmat,i,j,child.assigned);
pq.add(child);
}
}
}
return 0;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter the no. of clubs and students: ");
N=sc.nextInt();
int[][] cost=new int [N][N];
System.out.println("Enter the cost matrix: ");
for(int i=0;i<N;i++){
for(int j=0;j<N;j++) cost[i][j]=sc.nextInt();
}
System.out.println("\nOptimal Cost is " + findmin(cost));
}
}
