Page 1 of 5
10505 - Montesco vs Capuleto
Posted: Thu Jun 19, 2003 4:32 am
by witto
What should be the output for this input:
1
2
0
1 5
It seems that the judge input has something like that.
I've put an assert() to check that.
As for the algorithm, I'm trying to find all the bipartite components of the graph build from input and inviting the people from the bigger set of each bipartition. Does that solve the problem?
Thanks in advance,
Witto
Posted: Thu Jun 19, 2003 11:26 am
by Adrian Kuegel
You can ignore the numbers >n (it makes no difference if you do it or not if your algorithm is correct).
When you search for bipartite components, and you find out that they are not bipartite, do you mark all nodes in the component so that you don't use them again? That was my mistake.
If I understand your algorithm, it should solve the problem.
Solved...
Posted: Fri Jun 20, 2003 1:20 am
by witto
I was missing out something in the vertex coloring process....
I rewrote the function and got accepted.
Many thanks.
Is input correct?
Posted: Wed Jun 25, 2003 5:46 pm
by Alexander Kozlov
Is this input correct?
6
3 4 5 6
3 4 5 6
3 4 5 6
3 1 2 3
4 1 2 3 6
4 1 2 3 5
If YES what sould be the answer: 0 or 3?
My guess
Posted: Wed Jun 25, 2003 11:36 pm
by lucindo
My accepted program outpus '0' for this input
Re: My guess
Posted: Wed Jul 02, 2003 11:16 am
by windows2k
lucindo wrote:My accepted program outpus '0' for this input
What about the input?
3
6
1 2
2 3 1
1 4
2 1 2
3 1 2 3
1 1
6
2 23
1 3
1 1
1 6
1 4
0
8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0
thx
Posted: Wed Jul 02, 2003 5:50 pm
by lucindo
Hello windows2k,
The output of my program for this input is:
I used the algorithm that witto wrote above.
Posted: Thu Jul 03, 2003 6:09 pm
by windows2k
lucindo wrote:Hello windows2k,
The output of my program for this input is:
1
[/code]
I used the algorithm that witto wrote above.
Can you tell me why the ans is 1
8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0
if i choose 1 and 3 or 2 and 4,we can choose two
or i misunderstanding the meaning?
Re: My guess
Posted: Fri Jul 04, 2003 2:59 am
by witto
windows2k wrote:lucindo wrote:My accepted program outpus '0' for this input
What about the input?
3
(...)
thx
The output of my solution for that input is:
Good Luck
Re: My guess
Posted: Fri Jul 04, 2003 4:03 am
by windows2k
The output of my solution for that input is:
Good Luck[/quote]
To witto,My program outputs the same result
But I get WA:(
Could someone tell me what's wrong
[cpp]
#include <stdio.h>
#include <string.h>
bool graph[201][201];
char color[201];
int cc[2];
int n;
bool DFS(int node,int cn)
{
color[node]=cn;
cc[cn]++;
for(int i=1;i<=n;i++)
if(graph[node]
)
{
if(color==cn) return false;
if(color==-1)
{
if(!DFS(i,1-cn)) return false;
}
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(graph,false,sizeof(graph));
memset(color,0xff,sizeof(color));
for(int i=1;i<=n;i++)
{
int l,t;
scanf("%d",&l);
for(int j=0;j<l;j++)
{
scanf("%d",&t);
graph[t]=graph[t]=true;
}
}
int ans=0;
for(int i=1;i<=n;i++)
if(color==-1)
{
cc[0]=cc[1]=0;
if(!DFS(i,0)) continue;
if(cc[0]>cc[1]) ans+=cc[0];
else ans+=cc[1];
}
printf("%d\n",ans);
}
return 0;
}
[/cpp]
Posted: Sat Jul 05, 2003 3:38 am
by witto
Try doing a BFS insted of DFS... it worked for me.
hmm.. the code above
Posted: Sun Jul 13, 2003 7:03 pm
by huksy
I think you just made a mistake//
variable t is simply duplicated.
Re: hmm.. the code above
Posted: Mon Jul 14, 2003 9:24 am
by windows2k
huksy wrote:I think you just made a mistake//
variable t is simply duplicated.
I don't understand your meaning
Could you explain more clearly , thx
Posted: Mon Jul 14, 2003 12:25 pm
by huksy
outer while lv t & inner t
Posted: Mon Jul 14, 2003 4:09 pm
by windows2k
huksy wrote:outer while lv t & inner t
I have modified my code,but still get WA.
Maybe there exists some trick input? @@