This is a bipartite matching problem. This can be solved using Ford fulkerson algorithm for Max flow problem. #include <iostream> #include <limits.h> #include <string.h> #include <queue> using namespace std; int gr[500][500]; int rgr[500][500]; string str[50]; int h,w; int numOfantena; int parent[500]; bool visited[500]; int src,targt; bool bfs(int s, int t) { memset(visited, 0, sizeof(visited)); queue
Category: Bipartite Matching
663
Idea: Find the total number of matching and then check for every match(left,right) pair whether it is unique or not. To check this find total number of matching using the same algorithm just excluding a pair each time and compare the total number of founded match with the initial one. If it is not reduced
1194
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <vector> using namespace std; //int gr[105][105]; vector<int> gr[105]; int n,m,k; int rside[105],lside[105]; bool visit[105]; bool dfs(int pos) { for(int i=0;i<gr[pos].size();i++) { if(visit[gr[pos][i]]) continue; visit[gr[pos][i]] = 1; if(lside[gr[pos][i]]==-1 || dfs(lside[gr[pos][i]])) { rside[pos] = gr[pos][i]; lside[gr[pos][i]]= pos; return 1; } } return 0; } int main()
10080
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; int gr[105][105]; int N,M; double S,V; struct point{ double x; double y; }; point goph[105],hole[105]; // A DFS based recursive function that returns true if a // matching for vertex u is possible bool bpm(int u, bool seen[], int matchR[]) { // Try every