Page 1 of 3

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

Posted: Sat Nov 29, 2003 9:43 pm
by anup10000
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]

10092 - The Problem with the Problem Setter

Posted: Sat Nov 29, 2003 9:44 pm
by anup10000
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

thanx in advance.

Posted: Sun Nov 30, 2003 8:29 am
by junjieliang
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.

10092 Why this code gives w.a.

Posted: Sat Sep 18, 2004 8:06 am
by harry
i have solved several problems of bm using my modified ford fulkerson
algorithm.
but why the following code gives w.a.
plz help.thanks in advance.

Code: Select all

Code removed .Got A.C. :lol: 

Posted: Fri Sep 24, 2004 7:14 pm
by alu_mathics
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

Posted: Fri Sep 24, 2004 7:17 pm
by harry
Thanks a lot. :wink:
Finally i got A.C. :lol:

10092

Posted: Wed Feb 15, 2006 10:53 pm
by qndel
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;
}

If anybody see any mistake please help me.

Posted: Thu Feb 16, 2006 12:57 pm
by qndel
Or maybe someone knows any tricky input???

Posted: Thu Feb 16, 2006 1:16 pm
by qndel
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

Posted: Thu May 11, 2006 11:03 am
by m_thimma
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

Posted: Tue May 16, 2006 7:08 pm
by serur
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.

Posted: Tue May 16, 2006 9:43 pm
by mf
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

Posted: Tue May 16, 2006 10:15 pm
by serur
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/...

Posted: Tue May 16, 2006 10:54 pm
by mf
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.)

Posted: Wed May 17, 2006 7:38 am
by serur
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?

Your last suggestion about arrays is sound,of course,
but I only wanted to make my code a bit less messy :) while I debug it.