Page 2 of 2
Re:
Posted: Sun Oct 24, 2010 9:44 am
by sh415
mmonish wrote:jan >>
Thanks. I found my bugs and got AC.
i have found for which input my output is not correct ; but I cant find its solution..............
IS MY ALGORITHM OKEY::::
1: take input; if '0' is in set A ; then it will not enter in set A; if '0' is in set B then it should be eliminated from
B ;
2: if set A element has a multiple in set B ; then degree of element A and element B will increase;
3: now find the highest deg of any element; as it is highest it should be eliminated;
if it is in A[x]; then for each element in B if (B
%A[x]==0 ) then deg B decrease .deg A[x]=0;
else for each element of A if B[x]%A==0 then degree A decrease'; deg B[x]=0;
thus we eliminate one element;
4. repeat if while degree of all element is not zero.
shovon
Re: 11159 - Factors and Multiples
Posted: Sun Oct 24, 2010 3:38 pm
by sh415
i have found for which input my output is not correct ; but I cant find its solution..............
IS MY ALGORITHM OKEY::::
1: take input; if '0' is in set A ; then it will not enter in set A; if '0' is in set B then it should be eliminated from
B ;
2: if set A element has a multiple in set B ; then degree of element A and element B will increase;
3: now find the highest deg of any element; as it is highest it should be eliminated;
if it is in A[x]; then for each element in B if (B[i]%A[x]==0 ) then deg B[i] decrease .deg A[x]=0;
else for each element of A[i] if B[x]%A[i]==0 then degree A[i] decrease'; degree B[x]=0;
thus we eliminate one element;
4. repeat if while degree of all element is not zero.
shovon
Re: 11159 - Factors and Multiples
Posted: Mon Oct 25, 2010 12:37 pm
by sh415
sh415 wrote:i have found for which input my output is not correct ; but I cant find its solution..............
shovon
for some given sample input given by StatujaLeha
I found my code has +1 or +2 diffenence is some cases...................................
but the input are so long that i cant determinte where is the problem. need your help badly.................
Any advice or solution...............
shovon
Re: 11159 - Factors and Multiples
Posted: Fri Apr 18, 2014 6:07 am
by vsha041
Don't use ford-fulkerson/edmond-karp in its direct form to solve this problem or else you will get TLE. That's because these two are n^5. You can either use relabel to front or the algorithm explained here. Both of these are n^3.
http://www.geeksforgeeks.org/maximum-bi ... -matching/.
The later one is much easier to implement but is only valid for maximum cardinality bipartite matching. Relabel to front is n^3 and can solve any max-flow problem in general. Also remember that there can be zeros in the input. 0 is multiple of every number including 0 but no number (except for 0) is multiple of 0.
So if the input is
1
2 0 0
2 1 2
Answer will be 0.
but for input
1
2 1 2
2 0 0
answer will be 2.
Re: 11159 - Factors and Multiples
Posted: Thu May 28, 2015 10:44 am
by Tahanima
What is wrong with my code?
Code: Select all
#include <stdio.h>
#include <map>
#include <cstring>
#include <vector>
using namespace std;
int t,l,r;
map<int, vector<int> > graph;
int left[110], right[110], setA[110], setB[110];
bool flag[110];
bool matching(int u){
for(int i = 0; i<graph[u].size(); i++){
int v = graph[u][i];
if(flag[v]) continue;
flag[v] = true;
if(right[v] == -1 || matching(right[v])){
right[v] = u;
left[u] = v;
return true;
}
}
return false;
}
int bip_match(){
memset(left, 0, sizeof(left));
memset(right,-1,sizeof(right));
int cnt = 0;
for(int i = 0; i<l; i++){
memset(flag, 0, sizeof(flag));
if(matching(setA[i])) cnt++;
}
return cnt;
}
int main()
{
scanf("%d",&t);
for(int i = 1; i<=t; i++){
scanf("%d", &l);
for(int j = 0; j<l; j++){
scanf("%d", &setA[j]);
}
scanf("%d", &r);
for(int j = 0; j<r; j++){
scanf("%d", &setB[j]);
}
graph.clear();
for(int j = 0; j<l; j++){
for(int k = 0; k<r; k++){
if((setA[j]!=0 && setB[k]%setA[j] == 0) || setB[k] == 0){
graph[setA[j]].push_back(setB[k]);
}
}
}
printf("Case %d: %d\n", i, bip_match());
}
return 0;
}