#include <iostream> #include <string> #include <sstream> #include <fstream> #include <queue> #include <algorithm> #include <cstring> #include <set> using namespace std; int noOfelement; int mp[26]; string str,str1,str2; string output[2000]; int kk; bool gr[27][27]; stringstream ss; int elements[26]; set<string> SET; //ofstream out; bool check(int elemnt,bool visit[]) { for(int i=0;i<26;i++) { if(gr[i][elemnt] && mp[i]!=-1 && visit[mp[i]]==0) return 0; }
Category: Graph Algorithm
452
#include <iostream> #include <sstream> #include <string> #include <queue> #include <cstdio> #define INF 10000000 using namespace std; bool gr[26][26]; int daysreq[26],indegree[26]; int accumulated_days[26]; int t; int bfs(queue<int> q) { while(!q.empty()) { int a = q.front();q.pop(); for(int i=0;i<26;i++) { if(gr[a][i]) { accumulated_days[i]=max(accumulated_days[i],accumulated_days[a]+daysreq[i]); if(–indegree[i]==0) q.push(i); } } } int MX = 0; for(int i=0;i<26;i++) { MX = max(accumulated_days[i],MX);
10937
#include <cstdio> #include <queue> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <string> #define INF 10000 using namespace std; int location,target; vector<vector<int> > dp; int h,w; int graph[200][200]; string str[60]; struct POINT{ int x,y; }; POINT pp[3030]; POINT src,tr; int k; int dirx[4]={1,0,0,-1}; int diry[4]={0,1,-1,0}; int bfs(int s,int t) { int tmpy,tmpx; queue<int> q;
10349
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
10076
Problem description error: ∆T = ⌈β2(h2 − h1)⌉ + γ, if h1 < h2 , here if we use γ as problem description,we get WA from online judge,so use δ here to get accepted. #include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <cmath> #define INF 100000000 using namespace std; int M,N; int gr[20][20]; int dirx[4]={1,0,0,-1};
589
#include <iostream> #include <string.h> #include <string> #include <vector> #include <map> #include <queue> #include <cstdio> #include <cstdlib> #define ll long long #define INF 100000000 using namespace std; struct INFO{ string str; int CNT; int BX; int BY; int SX; int SY; }; int MX; string input[25]; int tx,ty; int r,c; string path=""; const int dirx[4]={-1,0,0,1}; const
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
532
#include <iostream> #include <string.h> #include <vector> #include <cstdio> #include <queue> #define ll long long #define INF 100000000 using namespace std; int gr[32][32][32]; bool visit[32][32][32]; int dist[32][32][32]; int x,y,z; int ex,ey,ez; int L,R,C; void bfs() { int tmp_x,tmp_y,tmp_z; queue<int> q; q.push(x); q.push(y); q.push(z); visit[x][y][z]=1; dist[x][y][z] = 0; while(!q.empty()) { tmp_x = q.front(); q.pop(); tmp_y = q.front();