## 10779 - Collectors Problem

Moderator: Board moderators

malioboro
New poster
Posts: 4
Joined: Sun Oct 05, 2014 10:52 am

### Re: 10779 - Collectors Problem

I had tried all testcase in this post, and got the correct answer

also I got correct answer for my other testcase:

Code: Select all

1
4 5
5 1 1 1 5 5
4 1 3 3 5
4 1 4 4 5
4 2 2 2 2

Code: Select all

Case #1: 4
but it still get verdict wrong answer in oj

my graph is divided in 3 part and that grouping the vertex :
- different sticker which Bob will trade
- N-1 friend
- different sticker which Bob will get
this is my code for build the graph with source=0 and sink=131 (i'm using standard edmond karp algorithm):

Code: Select all

...
cin>>k;
for(i=1; i<=k; i++)
{
cin>>a[i];
}

for(i=1; i<=28; i++)
{
}

for(i=0; i<n-1; i++)
{
cin>>t;
vi tmp;
tmp.clear();
memset(sk,0,sizeof sk);
for(j=0; j<t; j++)
{
cin>>l;
tmp.pb(l);
sk[l]++;
}

for(j=1; j<=m; j++)
{
if(!sk[j])
{
for(l=0; l<tmp.size(); l++)
{
if(sk[tmp[l]]>1)
{
}
}
}
}
}
...

thanks, sorry for my bad english

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10779 - Collectors Problem

Check input and AC output for thousands of problems on uDebug!

malioboro
New poster
Posts: 4
Joined: Sun Oct 05, 2014 10:52 am

### Re: 10779 - Collectors Problem

@Brianfry713 Sorry if i'm not post my full code, because I think the problem is in my graph construction.
I'mm only using template for the max flow. here is my code:

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <ctime>
#include <sstream>
using namespace std;
#define ot(x) cout<<x<<endl
#define cen cout<<endl
#define EPS 1e-10
#define mp(x,y) make_pair(x,y)
#define INF 1000000000
#define pb(x) push_back(x)
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<ii> vii;
priority_queue< pair<int, ii> > EdgeList;
int n,t,j,k,i,m,l,tc,itc;
int a[205], sk[205];

vi p;

void augment(int v, int minEdge)
{
if (v == s)
{
f = minEdge;
return;
}
else if (p[v] != -1)
{
}
}

int main ()
{
ios_base::sync_with_stdio(0);
cin>>tc;
itc=1;
while(tc--)
{
cin>>n>>m;
memset(a, 0, sizeof a);
cin>>k;
for(i=1; i<=k; i++)
{
cin>>a[i];
}

for(i=1; i<=28; i++)
{
}

for(i=0; i<n-1; i++)
{
cin>>t;
vi tmp;
tmp.clear();
memset(sk,0,sizeof sk);
for(j=0; j<t; j++)
{
cin>>l;
tmp.pb(l);
sk[l]++;
}

for(j=1; j<=m; j++)
{
if(!sk[j])
{
for(l=0; l<tmp.size(); l++)
{
if(sk[tmp[l]]>1)
{
}
}
}
}
}

mf = 0;
s=0;
t=131;
while (1)
{
f = 0;
vi dist(200, INF);
dist[s] = 0;
queue<int> q;
q.push(s);
p.assign(200, -1);
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == t) break;
for (int v = 0; v < 200; v++)
if (AdjMat[u][v] > 0 && dist[v] == INF)
dist[v] = dist[u] + 1, q.push(v), p[v] = u;
}
augment(t, INF);
if (f == 0) break;
mf += f;
}

cout<<"Case #"<<itc++<<": "<<mf<<"\n";
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10779 - Collectors Problem

I followed mf's post in this thread and got AC.
There are 520 nodes in the graph.
Each of the n subgraphs has a source, sink, in for each sticker, and out for each sticker.
Check input and AC output for thousands of problems on uDebug!

malioboro
New poster
Posts: 4
Joined: Sun Oct 05, 2014 10:52 am

### Re: 10779 - Collectors Problem

yeah, I read mf's post after I submit my code.
But I haven't tried his solution because I just wonder in what case my graph construction will be fail