I was searching for Assignment problem a lot and was not getting it .I tried to solve using Hungarian Algorithm but somehow no online code was available for it. Topcoder has provided with code snippets and implementation but it never worked out for me.

Here is best implementation for it.

 

Hungarian Algorithm.

#include <bits/stdc++.h>

using namespace std;

#define bug() printf(“BUG\n”)
#define bug1(n) cout<<“bg1 “<<n<<endl;
#define bug2(a,b) cout<<“bg2 “<<a<<” “<<b<<endl;
#define bug3(a,b,c) cout<<“bg3 “<<a<<” “<<b<<” “<<c<<endl;
#define MOD 1000000007
#define ll long long
#define vi vector< int >
#define vll vector< long long >
#define vvi vector< vector< int > >
#define vvll vector< vector< long long > >
#define pi pair< int, int >
#define pll pair< long long, long long >
#define vpi vector< pair< int, int > >
#define vpll vector< pair< long long, long long > >
#define pb(n) push_back(n)
#define mp(a,b) make_pair(a,b)
#define printA(a,n) for(int lolol = 0;lolol < n;++lolol) cout<<a[lolol]<<” “; cout<<endl;

int lines[55][55];

void print2A(int a[][55],int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
printf(“%d “,a[i][j] );
}
printf(“\n”);
}
}

int linesRequired(int a[55][55], int n)
{
int lll = (int)pow(2,2*n);
int mask[100] = {0};
int cpy[55][55];
int tlines[55][55] = {0};
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cpy[i][j] = a[i][j];
}
}
int miny = INT_MAX;
for (int i = 1; i <= lll; ++i)
{
int cnt = 0;
for (int k = i,j = 0; k > 0 && j < 2*n; k/=2,j++)
{
if (k%2 == 0)
mask[j] = 0;
else
{
mask[j] = 1;
cnt++;
}
}
if (cnt > n)
{
continue;
}
for (int k = 0; k < n; ++k)
{
if (mask[k] == 1)
{
for (int j = 0; j < n; ++j)
{
cpy[k][j] = 1; //row k
tlines[k][j] -= 1;
}
}
}
for (int k = n; k < 2*n; ++k)
{
if (mask[k] == 1)
{
for (int j = 0; j < n; ++j)
{
cpy[j][k-n] = 1; //column k-n
tlines[j][k-n] -= 1;
}
}
}
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
if (cpy[x][y] == 0)
{
goto here;
}
}
}
if (miny > cnt)
{
miny = cnt;
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
lines[x][y] = tlines[x][y];
}
}
}
if (miny < n)
{
return miny;
}
here:
{}
for (int x = 0; x < n; ++x)
{
for (int y = 0; y < n; ++y)
{
cpy[x][y] = a[x][y];
tlines[x][y] = 0;
}
}
}
return miny;
}

int minAlloc(int a[55][55],int actual[55][55],int n)
{
stack< pi >st;
vector< pair < int,pi > >m;
for (int i = 0; i < n; ++i)
{ //m[a,0] = 0 -> row a is assigned, m[a,0] = 1 -> row a is not assigned
m.pb(mp(0,mp(i,0))); //row
m.pb(mp(0,mp(i,1))); //column
}
int d = 1,prev = 1; //d = 1 -> forward, d = -1 -> backward
int xx = 0; //it has got some importance
int mask[55][55] = {0};
for (int i = 0,j; st.size() != n; ++i)
{
int flag = 0;
if (d == 1)
{
if (prev == -1)
{
j = xx;
}
else
j = 0;
for (; j < n; ++j)
{
if (a[i][j] == 0)
{
int po1 = find(m.begin(),m.end(),mp(0,mp(i,0))) – m.begin();
int po2 = find(m.begin(),m.end(),mp(0,mp(j,1))) – m.begin();
if (po1 < m.size() && po2 < m.size())
{
flag = 1;
st.push(mp(i,j));
m[po1].first = 1;
m[po2].first = 1;
goto here;
}
}
}
here:
{}
if (flag == 0)
{
if (prev == -1)
{
i–;
}
d = -1;
}
else
prev = 0;
}
if (d == -1)
{
prev = -1;
pi p = st.top();
st.pop();
int po1 = find(m.begin(),m.end(),mp(1,mp(p.first,0))) – m.begin();
int po2 = find(m.begin(),m.end(),mp(1,mp(p.second,1))) – m.begin();
m[po1].first = 0;
m[po2].first = 0;
mask[p.first][p.second] = 0;
i = p.first – 1;
xx = p.second + 1;
d = 1;
}
}
int ans = 0;
while(!st.empty())
{
pi p = st.top();
st.pop();
ans += actual[p.first][p.second];
}
return ans;
}

int main()
{
int n;
scanf(“%d”,&n);
int a[55][55];
int copy[55][55];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
scanf(“%d”,&a[i][j]);
copy[i][j] = a[i][j];
}
}
int miny;
for (int i = 0; i < n; ++i)
{
miny = a[i][0];
for (int j = 0; j < n; ++j)
{
miny = min(miny,a[i][j]);
}
for (int j = 0; j < n; ++j)
{
a[i][j] -= miny;
}
}
for (int i = 0; i < n; ++i)
{
miny = a[0][i];
for (int j = 0; j < n; ++j)
{
miny = min(miny,a[j][i]);
}
for (int j = 0; j < n; ++j)
{
a[j][i] -= miny;
}
}
int l = linesRequired(a,n);
while (l != n)
{
int minr = INT_MAX; //min of remaining.
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (lines[i][j] >= 0)
{
minr = min(minr,a[i][j]);
}
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (lines[i][j] >= 0)
{
a[i][j] -= minr;
}
if (lines[i][j] == -2)
{
a[i][j] += minr;
}
}
}
for (int i = 0; i < 55; ++i)
{
for (int j = 0; j < 55; ++j)
{
lines[i][j] = 0;
}
}
l = linesRequired(a,n);
}
int ans = minAlloc(a,copy,n);
cout<<ans<<endl;
return 0;
}

 

Input:-

3
4 15 20
7 10 19
7 20 4

Output:-

18

description:-

as 1->4,

2->10,

3->4

 

Advertisements