10092 - The Problem with the Problem Setter

[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]

[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.

[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.

[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: 

[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

[harry]

Thanks a lot.
Finally i got A.C.

[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.

[qndel]

Or maybe someone knows any tricky input???

[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

[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

[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.

Code: Select all

[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

[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/...

[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.)

[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.