Hi,
I thought of bipartite matching as possible solution , can any one tell me what is the correct algorithm to solve this problem.
Here is my code
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int inf=(1<<28);
double eps=1e-9;
double pi=acos(-1.0);
typedef vector<int> vi;
typedef long long int64;
typedef pair<int,int> ii;
#define size(x) (int)((x).size())
#define all(v) (v).begin(), (v).end()
#define For(i,x) for(int i=0;i<x;i++)
#define Forr(i,y,x) for(int i=y;i>=x;i--)
#define Forn(i,y,x) for(int i=y;i<=x;i++)
#define Fill(a, v) memset(a, v, sizeof(a))
#define outs(x) cout << #x << " = " << x << " ";
#define outn(x) cout << #x << " = " << x << "\n";
int n;
int prev[1001];
vi graph[1001];
int visit[1001];
int rank[1001];
string name[1001];
string ans[501][2];
int speciality[1001];
bool findNext(int x)
{
if(x<0)return true;
if(visit[x])return false;
visit[x]=1;
int sz = size(graph[x]);
For(i,sz)
{
int y = graph[x][i];
if(findNext(prev[y]))
{
prev[y]=x;
//prev[x]=y;
return true;
}
}
return false;
}
int main()
{
#ifdef FAMEOFLIGHT_HOME
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
// freopen("input2.txt","r",stdin);freopen("output2.txt","w",stdout);
#endif
int tmp;
char str1[30],str2[30];
scanf ("%d",&n);
For(i,n)
{
scanf ("%s %s %d",&str1,&str2,&tmp);
rank[i]=tmp;
name[i]=string(str1);
if(str2[0]=='a')speciality[i]=0;
if(str2[0]=='s')speciality[i]=1;
if(str2[0]=='t')speciality[i]=2;
}
// construct the graph
For(i,n)
{
For(j,n)
{
if(abs(rank[i]-rank[j])==2)
{
if(speciality[i]==0 || speciality[j]==0)graph[i].push_back (j) , graph[j].push_back (i);
else if((speciality[i]==1 && speciality[j]==2) || (speciality[i]==2 && speciality[j]==1))graph[i].push_back (j) , graph[j].push_back (i);
}
}
}
int ret=0;
Fill(prev,-1);
For(i,n)
{
Fill(visit,0);
findNext(i);
}
For(i,n)
{
if(prev[i]!=-1)
{
prev[prev[i]]=-1;
int x = i , y = prev[i];
ans[ret][0]=name[x];
ans[ret++][1]=name[y];
//printf ("%s %s\n",name[x].c_str (),name[y].c_str ());
}
}
printf ("%d\n",ret);
For(i,ret)
{
printf ("%s %s\n",ans[i][0].c_str (),ans[i][1].c_str ());
}
return 0;
}
