OJ Board

Posted: **Tue Feb 10, 2015 6:18 pm**

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

also I got correct answer for my other testcase:

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

that has correct answer:

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];
            AdjMat[0][a[i]]++;
            AdjMat[a[i]][a[i]+80]=1;
        }

        for(i=1; i<=28; i++)
        {
            AdjMat[i+80][131]=1;
        }

        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])
                {
                    AdjMat[j][i+30]=1;
                    for(l=0; l<tmp.size(); l++)
                    {
                        if(sk[tmp[l]]>1)
                        {
                            AdjMat[i+30][tmp[l]+80]=1;
                            AdjMat[i+30][tmp[l]]=sk[tmp[l]]-2;
                        }
                    }
                }
            }
        }
...

please help, if anybody have any cornercase, it will helpful

thanks, sorry for my bad english

Posted: **Wed Feb 11, 2015 10:42 pm**

post your full code.

Posted: **Thu Feb 12, 2015 6:35 am**

@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;
vector<vi> AdjList;
priority_queue< pair<int, ii> > EdgeList;
int n,t,j,k,i,m,l,tc,itc;
int a[205], sk[205];

int AdjMat[205][205], mf, f, s;
vi p;

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


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

        for(i=1; i<=28; i++)
        {
            AdjMat[i+80][131]=1;
        }

        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])
                {
                    AdjMat[j][i+30]=1;
                    for(l=0; l<tmp.size(); l++)
                    {
                        if(sk[tmp[l]]>1)
                        {
                            AdjMat[i+30][tmp[l]+80]=1;
                            if(AdjMat[0][tmp[l]]==0)AdjMat[i+30][tmp[l]]=sk[tmp[l]]-2;
                        }
                    }
                }
            }
        }

        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;
}

Posted: **Sat Feb 14, 2015 2:42 am**

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.

Posted: **Sat Feb 14, 2015 9:02 am**

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

OJ Board

10779 - Collectors Problem

Re: 10779 - Collectors Problem

Re: 10779 - Collectors Problem

Re: 10779 - Collectors Problem

Re: 10779 - Collectors Problem

Re: 10779 - Collectors Problem