OJ Board

Code: Select all

long touristsPerTrip = graph[start][end];
long trips = touristCount / touristsPerTrip;
if(touristCount % touristsPerTrip != 0) {
    trips++;
}

Code: Select all

numTrips = numTourists / maxPossibleBandwidth; 

Code: Select all

#include <iostream> 
#include <climits> 
#include <cstdlib> 
#include <list> 
using namespace std; 


// edge[i] = k 
// i is the node it is connected to 
// k is the bandwidth of that edge 
class Node {
public: 
    int edges[101];
};

class Edge {
public: 
    int toNode; 
    int bandwidth; 
};


void clearNodes(Node *nodes); 
void clearTable(int bandwidthTable[][101]); 

int main(void) 
{
    Node nodes[101]; //the array of nodes of our adjacency list 
    int bandwidthTable[101][101]; //the table of bandwidths for our algorithm
    Edge edges[101]; //edges used for finding maximum bandwidth

    int numCities,    // number of nodes in the graph
        numEdges,     // number of edges in the graph
        currNode1,    // first node scanned in
        currNode2,    // second node scanned in
        currBandwidth, // bandwidth between currNode1 and currNode2
        sourceNode,   // the number of our source node 
        destNode,     // the number of our destination node
        numTourists,  // the number of tourists to be taken on this trip
        numTrips, //the number of trips it will take... 
        maxPossibleBandwidth; //the maximum possible bandwidth

    cin >> numCities >> numEdges; 

    int caseNum = 1; 
    while(numCities != 0 || numEdges != 0) //outermost loop: for each case 
    {
        if(numCities == 0 || numEdges == 0)
        {
            numTrips = 0; 
            goto myContinue;
        }
        //graph input: 
        clearNodes(nodes); 
        clearTable(bandwidthTable); 
        for(int i = 0; i < numEdges; i++)
        {
            cin >> currNode1 >> currNode2 >> currBandwidth;
            currBandwidth--; 
            nodes[currNode1].edges[currNode2] = currBandwidth; 
            nodes[currNode2].edges[currNode1] = currBandwidth; 
        }
        //obtain the source node and the destination node 
        cin >> sourceNode >> destNode >> numTourists; 
        if(sourceNode == destNode)
        {
            numTrips = 0; 
            goto myContinue;
        }
        //set up the table 
        bandwidthTable[destNode][0]--; 
        //compute the bandwidth table
        int l; 

        for(int i = 1; i < numCities; i++) //for each number of edges 1 to n-1
        {
            for(int j = 1; j <= numCities; j++) //for each node 1 to n
            {
                l = 0; 
                for(int k = 1; k <= numCities; k++) //for each possible edge going from 1 to n
                {
                    //if the edge exists
                    if( (nodes[j].edges[k] != 0) && (bandwidthTable[k][i-1] < LONG_MAX))
                    {
                        edges[l].toNode = k;
                        edges[l].bandwidth = min(nodes[j].edges[k], bandwidthTable[k][i - 1]);
                        l++; 
                    }
                } //for each possible edge going from 1 to n 
                    //make the entry in the table 
                if(l)
                {
                    int currMaxBandwidth = 0; 
                    for(int m = 0; m < l; m++)
                        currMaxBandwidth = max(currMaxBandwidth, edges[m].bandwidth);
                    bandwidthTable[j][i] = currMaxBandwidth; 
                }
            } //for each node 1 to n
        }//for each number of edges 0 to n-1 

        //you now have your table complete. 
        maxPossibleBandwidth = 0; 
        for(int i = 1; i < numCities; i++)
            if(bandwidthTable[sourceNode][i] < LONG_MAX)
                maxPossibleBandwidth = max(maxPossibleBandwidth, bandwidthTable[sourceNode][i]); 

        numTrips = numTourists / maxPossibleBandwidth; 
        if(numTourists % maxPossibleBandwidth > 0)
            numTrips++; 

myContinue: 
        cout << "Scenario #" << caseNum << '\n' << "Minimum Number of Trips = " << numTrips << "\n\n"; 
        //ends with: 
        caseNum++; 
        cin >> numCities >> numEdges; 
    } //outermost loop: for each case
    return 0; 
}



//all used edge bandwidths are greater than 0, so we can clear out the 
//bandwidths between each test case by resetting them to zero. 
void clearNodes(Node *nodes)
{
    for(int i = 0; i < 101; i++)
        for(int j = 0; j < 101; j++)
            nodes[i].edges[j] = 0; 
}

void clearTable(int bandwidthTable[][101])
{
    for(int i = 0; i < 101; i++)
        for(int j = 0; j < 101; j++)
            bandwidthTable[i][j] = LONG_MAX; 
}

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>

#define fr(a, b, c) for(int a = b; a <= c; a++)
#define mst(a, b) memset(a, b, sizeof(a));

using namespace std;

typedef struct {
    int parent;
    list <int> adj;
}nod;
typedef struct {
    int from;
    int to;
    int weight;
}vert;
vert edge[1008];
int parent[1002];
nod node[1005];
int adj[1003][1003];
int find_parent(int a)
{
    if(parent[a] == a)
     return a;
    else
        parent[a] =  find_parent(parent[a]);
}
int is_union(int a, int b)
{
    return (find_parent(a) == find_parent(b));
}
void make_union(int c1, int c2)
{
    parent[find_parent(c1)] = find_parent(c2);
}
int comp ( const void *a, const void*b)
{
if( ( * ( vert* ) a ).weight < ( *( vert* )b ).weight )
return 1;
return -1;
}

void min_span_tree(int n)
{
    fr(i, 1, 1004)
        parent[i] = i;
    //cout << "going to sort\n";
    qsort(edge, n, sizeof(vert), comp);
    //cout << "sorted\n\n";
    fr (i, 1, n){
        if(!is_union(edge[i].from, edge[i].to)) {
            make_union(edge[i].from, edge[i].to);
            node[edge[i].from].adj.push_back(edge[i].to);
            node[edge[i].to].adj.push_back(edge[i].from);
            //cout << "\nConnectiong nodes " << edge[i].from << " and " << edge[i].to;
        }
    }
}
int min_passenger(int a, int b)
{
    int min = 10e8;
    int temp = node[b].parent;
    while(1){
        if(temp == a){
            if(adj[b][temp] < min)
                min = adj[b][temp];
            break;
        }
        else{
            if(adj[temp][b] < min)
                min = adj[temp][b];
            b = temp;
            temp = node[temp].parent;
        }
    }
    return min;
}
int bfs_mod(int a, int b, int n)
{
    int visited[1003];
    int count = 0, kk = 0;
    mst(visited, 0);
    queue <int> q;
    fr(i, 1, n)
        node[i].parent = 0;
    list <int> :: iterator it;
    fr(i, a, n){
        if(visited[i] == 0) {
            visited[i] =1;
            q.push(i);
        }
        while(!q.empty()){
            kk = q.front();
            q.pop();
            //cout << "Currently on node " << kk << endl;
            //system("pause");
            for(it = node[kk].adj.begin(); it != node[kk].adj.end(); it++){
                if(!visited[*it]){
                    visited[*it] = 1;
                    q.push(*it);
                    node[*it].parent = kk;
                }
            }
        }
    }
    return min_passenger(a, b);
}
void clear_all ()
{
    //mst(a, 0);
    mst(parent, 0);
    mst(adj, 0);
    fr(i, 1, 1002) {
        node[i].parent = 0;
        node[i].adj.clear();
    }
    fr(i, 1, 1003){
        edge[i].from = 0;
        edge[i].to = 0;
        edge[i].weight = 0;
    }
}
void print_all(int c, int s)
{
    cout << "Printing the edges \n";
    fr(i, 1, s){
        cout << "\n\nfrom " << edge[i].from ;
        cout << "   to " << edge[i].to;
        cout << "   weight id " << edge[i].weight;
    }
    cout << "\n";
    cout << "Printing arents of all nodes\n";
    fr(i, 1, c)
        cout << parent[i] << "   ";
    cout << "\n\nPrinting the nodes adjacency list\n";
    fr(i, 1, c){
        cout << "\nPrinting ajcancy list for node " << i << endl;
        list <int> :: iterator it;
        for(it = node[i].adj.begin(); it != node[i].adj.end(); it++)
            cout << *it << "    ";
    }
}
int main()
{
    int c, s, q, t = 1;
    while (1){
        int x, y, w;
        scanf("%d %d", &c, &s);
        if(c == 0 && s == 0)
            break;
        clear_all();
        cout << "Scenario #" << t << endl;;
        t++;

        //mst(a, 0);
        fr(i, 1, s){
            scanf("%d %d %d", &x, &y, &w);
            edge[i].from = x;
            edge[i].to = y;
            edge[i].weight = w;
            adj[y][x] = w;
            adj[x][y] = w;
        }

        min_span_tree(s);
        //print_all(c, s);
        //fr(i, 1, q){
        scanf("%d %d %d", &x, &y, &q);
        int mini = ceil(q / (bfs_mod(x, y, c)-1));
        cout << "Minimun Number of Trips = " << mini << endl;
        cout << "\n";
        //break;
    }
}