Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<time.h>
- #include<cstdlib>
- #include<vector>
- #include<fstream>
- #define infinity 10000
- #define node int
- using namespace std;
- void bnb(int n);
- int bnbfirst(void);
- int calculateLocalCost(int x,int y);
- int mat[1000][1000];
- int n;
- int basic;
- int cost=infinity;
- vector<node> optimal;
- int main(void)
- {
- ifstream myfile2;
- myfile2.open("input6.txt");
- cout<<"Input the size of graph: "<<endl;
- myfile2>>n;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- myfile2>>mat[i][j];
- }
- }
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- cout<<mat[i][j]<<'\t';
- }
- cout<<endl;
- }
- basic=bnbfirst(); ///calculate initial node cost
- cout<<basic<<endl;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- cout<<mat[i][j]<<'\t';
- }
- cout<<endl;
- }
- optimal.push_back(0);
- bnb(0);
- for(int i=0;i<optimal.size();i++)
- {
- cout<<optimal[i]<<' ';
- }cout<<endl;
- }
- int bnbfirst(void)
- {
- int cost=0;
- for(int i=0;i<n;i++)
- {
- int low=infinity;
- for(int j=0;j<n;j++) ///lowest determined
- {
- if(mat[i][j]<low)
- {
- low=mat[i][j];
- }
- }
- for(int j=0;j<n;j++) ///low is subtracted from all elements of the row
- {
- if(mat[i][j]==infinity);
- else
- {
- mat[i][j]-=low;
- }
- }
- cost+=low;
- }
- for(int j=0;j<n;j++)
- {
- int low=infinity;
- for(int i=0;i<n;i++) ///lowest determined
- {
- if(mat[i][j]<low)
- {
- low=mat[i][j];
- }
- }
- for(int i=0;i<n;i++) ///low is subtracted from all elements of the column
- {
- if(mat[i][j]==infinity);
- else
- {
- mat[i][j]-=low;
- }
- }
- cost+=low;
- }
- return cost;
- }
- void bnb(int x)
- {
- int localcost=infinity,next;
- for(int i=0;i<n;i++)
- {
- int flag=0;
- for(int j=0;j<optimal.size();j++) ///check if the node is already in the path
- {
- if(i==optimal[j])
- {
- flag=1;
- break;
- }
- }
- if(flag==0)
- {int cc=calculateLocalCost(x,i);
- cout<<"cc "<<cc<<endl;
- if(localcost>cc)
- {
- localcost=cc;
- cout<<"local "<<localcost<<endl;
- next=i;
- cout<<"next "<<next<<endl;
- }
- }
- }
- basic+=localcost;
- cout<<"basic "<<basic<<endl;
- optimal.push_back(next);
- cout<<"next push to vector "<<next<<endl;
- for(int i=0;i<n;i++) ///row of x turned infinity
- {
- mat[x][i]=infinity;
- }
- for(int i=0;i<n;i++) ///column of next turned infinity
- {
- mat[i][next]=infinity;
- }
- mat[x][next]=mat[next][x]=infinity;
- int low=infinity;
- for(int i=0;i<n;i++)
- {
- if(low>mat[0][i])
- {
- low=mat[0][i];
- }
- }
- for(int i=0;i<n;i++)
- {
- mat[0][i]-=low;
- }
- cout<<"next "<<next<<endl;
- if(optimal.size()==n) return;
- bnb(next);
- }
- int calculateLocalCost(int x,int y)
- {
- int temp[n][n];
- int low=infinity;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- temp[i][j]=mat[i][j];
- }
- }
- //
- // cout<<"<<inside>>\n";
- // cout<<x<<' '<<y<<endl;
- // for(int i=0;i<n;i++)
- // {
- // for(int j=0;j<n;j++)
- // {
- // cout<<mat[i][j]<<'\t';
- // }cout<<endl;
- // }
- // cout<<"<<inside>>\n";
- int localcost=temp[x][y];
- for(int i=0;i<n;i++)
- {
- if(temp[x][i]<low)
- {
- low=temp[x][i];
- }
- }
- localcost+=low;
- return localcost;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement