1172 - The Bridges of Kolsberg

[Degiac]

Has someone got some tricky test cases for this problem? I keep getting WA and I can't realize why. I wrote some test cases myself but I always get the right answer

EDIT: nvm, solved

[brianfry713]

I added some random input at:
http://www.udebug.com/UVa/1172

[bradd123]

Hi, Can anybody tell me How to proceed to solve this problem? It looks like matching with some constraints. Please give me some hints?

[Ahmad_Elsagheer]

Hey guys,

I solved this problem and only got accepted after considering the constraint: no city could be an endpoint of more than one bridge. Does the problem description imply this constraint ? If anyone got accepted without considering such a constraint, I would appreciate telling me briefly his algorithm to look for my bug, if any.

Thanks

[Shafayat]

Why I'm getting WA?
I've submitted without comments.

Code: Select all

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct bridge
{
    long long int cost;
    char city[1000],os[1000];
}le[1000],ri[1000];     //store inputs. 'le' for first bank and 'ri' for second bank

struct table
{
    long long int pos;
    long long int co;   // stores the cost
    long long int cou;  // count the bridge
}tab[1000][1000];         //table for current maximum cost and minimum number of bridge

/* in this solve function I use algorithm like coin change algorithm.
here, I create a table.
for all bridges in 're', i choose bridge from 'le' and find current maximum cost and minimum number of bridge.*/

void solve(long long int a,long long int b)
{
    memset(tab,0,sizeof(tab));
    for(long long int i=0;i<a;i++)     //Select bridge from le
    {
        for(long long int j=0;j<b;j++)   //Select bridge from re
        {
            if(strcmp(le[i].os,ri[j].os)==0)      // compare OS name
            {
                if((tab[i][j].co+le[i].cost+ri[j].cost)>tab[i][j+1].co && (tab[i][j].co+le[i].cost+ri[j].cost)>tab[i+1][j].co)  // check if (cost stored in previous diagonal cost from table+ cost of current bridge) is greater than cost stored in upward position and left position of the table
                {
                    tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
                    tab[i+1][j+1].pos=j+1;   // stores the position where I get current maximum
                    tab[i+1][j+1].cou=tab[i][j].cou+1;   // count the bridge number

                }
                else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i][j+1].co)   // if current cost and cost of upward position in table is same than choose that one which contains minimum number of bridge
                {
                    tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
                    if((tab[i][j].cou+1)<tab[i][j+1].cou)
                    {
                        tab[i+1][j+1].pos=j+1;
                        tab[i+1][j+1].cou=tab[i][j].cou+1;
                    }
                    else
                    {
                        tab[i+1][j+1].pos=tab[i][j+1].pos;
                        tab[i+1][j+1].cou=tab[i][j+1].cou;
                    }

                }
                else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i+1][j].co)  // if current cost and cost of left position in table is same
                {
                    tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
                    if((tab[i][j].cou+1)<tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].pos=j+1;
                        tab[i+1][j+1].cou=tab[i][j].cou+1;
                    }
                    else
                    {
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }

                }
                // conditions after this line works if (cost stored in previous diagonal cost from table+ cost of current bridge) is smaller than upward and left position
                else if(tab[i][j+1].co>tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i][j+1].co;
                    tab[i+1][j+1].pos=tab[i][j+1].pos;
                    tab[i+1][j+1].cou=tab[i][j+1].cou;
                }
                else if(tab[i][j+1].co<tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i+1][j].co;
                    tab[i+1][j+1].pos=tab[i+1][j].pos;
                    tab[i+1][j+1].cou=tab[i+1][j].cou;
                }
                else
                {
                    if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou<tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i][j+1].co;
                        tab[i+1][j+1].pos=tab[i][j+1].pos;
                        tab[i+1][j+1].cou=tab[i][j+1].cou;
                    }
                    else if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou>tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                    else
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                }
            }
            else    // if OS name does not matches than I choose from upward and left position
            {
                if(tab[i][j+1].co>tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i][j+1].co;
                    tab[i+1][j+1].pos=tab[i][j+1].pos;
                    tab[i+1][j+1].cou=tab[i][j+1].cou;
                }
                else if(tab[i][j+1].co<tab[i+1][j].co)
                {
                    tab[i+1][j+1].co=tab[i+1][j].co;
                    tab[i+1][j+1].pos=tab[i+1][j].pos;
                    tab[i+1][j+1].cou=tab[i+1][j].cou;
                }
                else
                {
                    if(tab[i][j+1].cou<tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i][j+1].co;
                        tab[i+1][j+1].pos=tab[i][j+1].pos;
                        tab[i+1][j+1].cou=tab[i][j+1].cou;
                    }
                    else if(tab[i][j+1].cou>tab[i+1][j].cou)
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                    else
                    {
                        tab[i+1][j+1].co=tab[i+1][j].co;
                        tab[i+1][j+1].pos=tab[i+1][j].pos;
                        tab[i+1][j+1].cou=tab[i+1][j].cou;
                    }
                }
            }
        }
    }

}

int main()
{
    long long int a,b,c,d,e,f,g,h;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>a;
    for(b=1;b<=a;b++)
    {
        cin>>c;
        for(d=0;d<c;d++)
        {
            cin>>le[d].city>>le[d].os>>le[d].cost;
        }
        cin>>d;
        for(e=0;e<d;e++)
        {
            cin>>ri[e].city>>ri[e].os>>ri[e].cost;
        }
        solve(c,d);
        for(int i=0;i<=c;i++)
        {
            for(int j=0;j<=d;j++)
            {
                printf("%8lld-%lld ",tab[i][j].co,tab[i][j].cou);
            }
            cout<<endl;
        }
        printf("%lld %lld\n",tab[c][d].co,tab[c][d].cou);
    }
    return 0;
}

[metaphysis]

Be careful of the boundary condition.