11749 - Poor Trade Advisor

[jakir.duet]

Can anybody explain this problem? I didn't understand at all what it wanted.

[t2faz]

it's a simple DFS problem....
but you have to suffer if u don't initialize the graph by a big negative number.
coz PPA may be negative.

[Shafaet_du]

The description is not good though its a nice problem. You need to find the largest connected component with highest average PPA in this problem. And you will get the highest average only if you take the max weight edges .

[brianfry713]

I believe there is a case like this in the input. With a repeat road, be sure to store the maximum.

Code: Select all

3 3
2 1 0
2 1 -1
1 3 0
0 0

AC Output:
3

[magurmach]

A very disgusting problem with this one is... we have to initialize the adjacency matrix with Minimal number (better -2147483647) at first I initialized with -999999999 got WA... changed total code still WA and then just changed the limit and got AC and in exchange of 8 WA I got 2nd rank!!!

[Scarecrow]

can't find why getting WA. please someone help me find the case where the code fails

Code: Select all

AC

[Scarecrow]

can't anyone help?

[remerson]

You don't need to initialise the PPA value with an arbitrary negative value because the problem states clearly that M > 0 so there will always be an initial edge to initialise from.

It is a nice problem but the description is not the easiest to follow and bit confusing. The term "average" is very misleading. Ignore all roads which do not have maximal PPA.

Bear in mind also that there can be more than 1 connected component containing the same number of cities with maximal PPA. The second example input case shows this i.e. more than 1 province but all with equal cardinality. Draw it out to see (I did and it was helpful).

It is possible also to solve this with disjoint sets union/find.

I think the judge input tests the full range of M i.e. up to 1M edges which is quite a large input.

I can post some test input cases if anyone is still stuck or otherwise it is available on UVA Toolkit for you to check arbitrary test cases.

As Brian says, there are definitely cases of repeated roads. You can infer this from the problem description because M <= 1M but N is only <= 500 and a complete graph with 500 nodes only has 125250 edges (I think!) which is << 1M, so there must be repeated roads.

Be sure to test edge cases like maximal PPA is negative and complete/disconnected PPA graphs etc.

For added realism, you can also run your laptop on battery just like the problem says and see if you can complete it in time!

[Scarecrow]

Thanks remerson! Got AC using Union-Find Disjoint Sets And the fault in the DFS solution was initializing ppamax by -2147483647.

[dipdeb]

Code: Select all

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int ar[1000005],br[1000005],cr[1000005],graph[505][505];
int visited[505],n,m,temp;

void dfs(int i){
    for(int j=1;j<=n;j++){
        if(graph[i][j]&&!visited[j]){
            visited[j]=1;
            temp++;
            dfs(j);
        }
    }
}
int main(){
    int i,j,max_ppa,cities;
    while(scanf("%d %d",&n,&m)!=EOF){
        if(n==0&&m==0)break;
        max_ppa=-1;
        for( i=1;i<=m;i++){
            scanf("%d %d %d",&ar[i],&br[i],&cr[i]);
            max_ppa=max(max_ppa,cr[i]);
        }
        memset(graph,0,sizeof(graph));
        memset(visited,0,sizeof(visited));
        for( i=1;i<=m;i++){
            if(max_ppa==cr[i]){
                graph[ar[i]][br[i]]=graph[br[i]][ar[i]]=1;
            }
        }

         cities=-1;
        for( i=1;i<=n;i++){
            if(!visited[i]){

                temp=1;
                visited[i]=1;
                dfs(i);
                cities=max(cities,temp);

            }
        }
        printf("%d\n",cities);
    }

}

[brianfry713]

Change line 22 to:
max_ppa = -2147483648;