10092 - The Problem with the Problem Setter

Moderator: Board moderators

anup10000
New poster
Posts: 2
Joined: Fri Oct 18, 2002 11:28 am
Contact:

10092 plz help(is it a max flow problem by any chance?)

is it really a max flow problem? though i m not convinced about that, i tried doing it by ford fulkerson but could only get TLE. but i m not yet convinced abt the problem being a max flow problem. can anybobdy plz give share the algo and a brief explanation for the problem[/b]

anup10000
New poster
Posts: 2
Joined: Fri Oct 18, 2002 11:28 am
Contact:

10092 - The Problem with the Problem Setter

is it really a max flow problem?
though i m not convinced about that, i tried doing it by ford fulkerson but could only get TLE. but i m not yet convinced abt the problem being a max flow problem.
can anybobdy plz give share the algo and a brief explanation for the problem

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
You can solve this problem by modifying the bipartite matching algorithm. But my friend also managed to solve this as max-flow, so perhaps you could optimise your ford fulkerson slightly to pass the time limit?

Both are quite slow though, modified bipartite matching used 0:03.096, 560 memory. Max-flow used 0:05.525, 12632 memory. You can even solve this faster by using hopcraft karp.

Hope this helps.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

10092 Why this code gives w.a.

i have solved several problems of bm using my modified ford fulkerson
algorithm.
but why the following code gives w.a.

Code: Select all

``````Code removed .Got A.C. :lol:
``````
Last edited by harry on Fri Sep 24, 2004 7:18 pm, edited 1 time in total.

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
i thing you should not do that

list[s][count[s]++] = i;
//list[count++] = s;

change it to
list[s][count[s]++] = i;
list[count++] = s;

Hope you will get ac for that.Oh one thing , set max = 1022
cuii e

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK
Thanks a lot.
Finally i got A.C.

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

10092

I'm trying to solve problem 10092 but I'm getting WA. I'm buildig graph like this:

conect every category with sink (capicty= numbers of problems for this category).
if problem i is in category j I conect (j,i) (capicty=1) and fianlly I conect evry problem with the sink (capicty=1).

and find max flow using Ford Fulkerson method.

This is my code:

Code: Select all

``````#include <stdio.h>
#include <vector>

using namespace std;

int min(int a,int b)
{
if (a>b)
return b;
else
return a;
}

int p,k,i,t,temp,j;
vector<int> graf[1100];
int f[1100][1100],obj[1100][1100];
bool byl[1100];

int dfs(int co,int juz)
{
byl[co]=true;
int t,temp,t2;
if (co==(p+k+1))
return juz;
for (i=0;i<graf[co].size();i++)
if (byl[graf[co][i]]==false)
{
t=graf[co][i];
temp=min(juz,obj[co][t]-f[co][t]+f[t][co]);
if (temp<=0)
continue;
t2=dfs(t,temp);
if (t2>0)
{
temp=min(t2,f[t][co]);
f[t][co]-=temp;
f[co][t]+=t2-temp;
return t2;
}
}
return 0;
}

int main()
{
while (1)
{
scanf("%d %d",&k,&p);
if (k==0 && p==0)
break;
for (i=0;i<=k+p+1;i++)
graf[i].clear();
memset(&obj,0,1100*1100*sizeof(int));
memset(&f,0,1100*1100*sizeof(int));
for (i=1;i<=k;i++)
{
scanf("%d",&t);
graf[0].push_back(i);
obj[0][i]=t;
}
for (i=1;i<=p;i++)
{
scanf("%d",&t);
graf[k+i].push_back(k+p+1);
obj[k+i][k+p+1]=1;
for (j=1;j<=t;j++)
{
scanf("%d",&temp);
graf[k+i].push_back(temp);
graf[temp].push_back(k+i);
obj[temp][k+i]=1;
}
}
memset(&byl,0,1100*sizeof(bool));
while (dfs(0,10000))
memset(&byl,0,1100*sizeof(bool));
bool bb=false;
for (i=1;i<=k;i++)
if (f[0][i]<obj[0][i])
{
printf("0\n");
bb=true;
break;
}
if (bb)
continue;
printf("1\n");
for (i=1;i<=k;i++)
{
bool b=false;
for (j=1;j<=p;j++)
if (f[i][k+j]>0)
{
if (b)
printf(" ");
b=true;
printf("%d",j);
}
printf("\n");
}
}
return 0;
}
``````

NOthing special

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole
Or maybe someone knows any tricky input???
NOthing special

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole
What is correct output for:
8 20
1 3 3 4 5 1 3 3
6 1 2 3 4 5 6
5 1 2 3 4 5
8 1 2 3 4 5 6 7 8
2 1 2
1 1
1 1
7 1 2 3 4 5 6 7
1 1
6 1 2 3 4 5 6
2 1 2
2 1 2
1 1
4 1 2 3 4
2 1 2
6 1 2 3 4 5 6
2 1 2
6 1 2 3 4 5 6
6 1 2 3 4 5 6
3 1 2 3
7 1 2 3 4 5 6 7
2 5
3 5
2 1 2
1 1
1 1
2 1 2
2 1 2
9 18
3 5 4 1 2 4 1 3 3
4 1 2 3 4
3 1 2 3
9 1 2 3 4 5 6 7 8 9
3 1 2 3
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7
6 1 2 3 4 5 6
1 1
6 1 2 3 4 5 6
8 1 2 3 4 5 6 7 8
4 1 2 3 4
9 1 2 3 4 5 6 7 8 9
3 1 2 3
4 1 2 3 4
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7 8
1 8
3
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
4 19
2 3 4 1
4 1 2 3 4
1 1
4 1 2 3 4
1 1
4 1 2 3 4
1 1
2 1 2
1 1
3 1 2 3
3 1 2 3
4 1 2 3 4
1 1
1 1
3 1 2 3
1 1
3 1 2 3
2 1 2
4 1 2 3 4
1 1
10 19
2 1 5 1 1 2 1 3 1 5
5 1 2 3 4 5
9 1 2 3 4 5 6 7 8 9
6 1 2 3 4 5 6
10 1 2 3 4 5 6 7 8 9 10
10 1 2 3 4 5 6 7 8 9 10
8 1 2 3 4 5 6 7 8
5 1 2 3 4 5
8 1 2 3 4 5 6 7 8
10 1 2 3 4 5 6 7 8 9 10
7 1 2 3 4 5 6 7
4 1 2 3 4
3 1 2 3
4 1 2 3 4
3 1 2 3
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
10 1 2 3 4 5 6 7 8 9 10
6 1 2 3 4 5 6
9 1 2 3 4 5 6 7 8 9
8 14
4 4 1 3 3 5 3 1
3 1 2 3
1 1
3 1 2 3
8 1 2 3 4 5 6 7 8
2 1 2
5 1 2 3 4 5
3 1 2 3
5 1 2 3 4 5
5 1 2 3 4 5
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
3 1 2 3
2 1 2
4 1 2 3 4
2 7
4 2
1 1
1 1
2 1 2
1 1
2 1 2
1 1
1 1
3 11
4 4 4
3 1 2 3
2 1 2
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
1 1
1 1
1 1
3 1 2 3
3 1 2 3
2 11
1 4
1 1
1 1
2 1 2
1 1
1 1
1 1
2 1 2
2 1 2
1 1
1 1
2 1 2
0 0

my is
0
0
0
1
1 2 3
1
2 8
7 11 14
3 5 9 10
1
0
0
1
1 2 4 6
3 5
0
1
1
3 7 8 11
NOthing special

m_thimma
New poster
Posts: 3
Joined: Wed Feb 15, 2006 10:01 am
Location: iitg,india
i used edmond-karps algrorithm...
i got a timelimit of 0.033sec for software allocation...
i used same alg with little modifications to this problem....
but i am getting 2.5sec....
can anyone suggest some ways to reduce my running time
Genius is a 2% inspiration and 98% perspiration

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hi fellows!

I'm learning preflow-push as it is expounded in "Bible" , and got AC the "touchstone" of network flow algoritms - q820 - "Internet Bandwidth". I applied preflow-push to 10092 (because Edmund-Karp gave TLE...), and I think found "official solution",for my outputs for sample inputs were the same as in problem description, but OJ says WA.
Fellows who solved 10092 with preflow-push - your comments will be greatly appreciated.

I attach my code. I think it's just what's written in pseudocode in CLR.
One comment: when solving this with Edmund-Karp I made links unidirectional, but here I was obliged to make them bidirectional. What do you think of it all?

Thank you.
Last edited by serur on Wed May 17, 2006 7:39 am, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
here I was obliged to make them bidirectional. What do you think of it all?
Well, the maximum flow will be equal to max cardinality of matching anyway, but if edges are bidirectional you can't convert the flow to a matching in that way as you do now. The output may not be a matching.

Here's a simple test, your output (all 1's) is wrong.

Code: Select all

``````3 3
1 1 1
3 1 2 3
3 1 2 3
3 1 2 3
0 0
``````

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Thank you, mf.

Tomorrow I'll think of all you said thoroughly.
And tell you what came of it
But, you see, when I made them unidirectional, my program got into infinite loop for second sample test - I suppose my implementation of preflow-push is wrong? But the same code got AC in 820/...
Last edited by serur on Sat Apr 14, 2012 3:28 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
So why didn't you try to debug? Infinite loops definitely indicate some problem with code, and if you don't take the time to analyze what causes it, the bug may hit you again and again.

I see at least one bug: in init_preflow() you change flow along edges outgoing from source, but you don't update the residual capacity array.

(Actually, what's the point of having two separate arrays for flow and residual capacity? Just keep one array, say residual capacity; you can always find the flow by subtracting residual from initial capacity.)

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Well, mf, "Utro vechera mudrenee". I just got AC with 1.777 ( )
I changed this: made all the edges directed except edges between source and categories - so that is some category is overflowing it can send liquid to the source agin. It's complete biparite matching problem, yes?