Problem 1: Even? Odd? [25 points] [Rob Kolstad, 2009]

#define MAXP 1000

// DFS: {x-visiting node, d-depth} -- recursive

void visit(int x, int d) {

if (x==0) return; // if the node is a pasture

if (maxpath < d) maxpath=d; // update the longest path
visit (l[x],d+1); // branch to left

visit (r[x],d+1); // branch to right

}
int main () {

// read in the data:

ifstream f("stroll.in");

f >> p;

int a, b, c;

f >> a >> b >> c;

l[a] = b;

r[a] = c;

}

f.close();

visit (1,1);

ofstream f ("stroll.out");

f << maxpath << "\n";

f.close();

}
Двоичното дърво е частен случай на граф. Нека обобщим задачата за граф: Измежду всички прости пътища от връх 1 до N+1 се търси най-дългия по брой на върховете.
Алгоритъмът за намиране на всички прости пътища между два върха, който аз използвах за решение на тази задача е детайлно обяснен в „Програмиране = ++Aлгоритми”, глава 5, стр. 264-266. Ето и моето решение:

#include

#define MAXN 1005
int N, startV = 1, endV, count, answer = 0;

bool A[MAXN][MAXN], used[MAXN];

{

if (i == j)

if(count > answer) answer = count;

return;

}
used[i] = true;

for (int k = 0; k < N; k++)

if (A[i][k] && !used[k]) allDFS(k, j);

used[i] = false;

count--;

}
int main()

{

FILE * f = fopen("stroll.in", "r");

for(int i = 0;i < N - 1;i++)

{

fscanf(f, "%d %d %d\n", &a, &b, &c);

{

A[a - 1][b - 1] = true;

}
if(c > 0)

{

A[a - 1][c - 1] = true;

}

}

allDFS(startV - 1, N - 1);

return 0;

}
Problem 8: Bessie's Weight Problem [250 points] [Rob Kolstad (traditional), 2009]
Bessie, like so many of her sisters, has put on a few too many pounds enjoying the delectable grass from Farmer John's pastures. FJ has put her on a strict diet of no more than H (5 <= H <= 45,000) kilograms of hay per day.
Bessie can eat only complete bales of hay; once she starts she can't stop. She has a complete list of the N (1 <= N <= 500) hay bales available to her for this evening's dinner and, of course, wants to maximize the total hay she consumes. She can eat each supplied bale only once, naturally (though duplicate weight values might appear in the input list; each of them can be eaten one time).
Given the list of hay bale weights W_i (1 <= W_i <= H), determine the maximum amount of hay Bessie can consume without exceeding her limit of H kilograms (remember: once she starts on a hay bale, she eats it all).
POINTS: 250
PROBLEM NAME: diet
INPUT FORMAT:
* Line 1: Two space-separated integers: H and N
* Lines 2...N+1: Line i+1 describes the weight of hay bale i with a single integer: W_i
SAMPLE INPUT (file diet.in):
56 4

15

19

21
INPUT DETAILS:

#include "stdio.h";

#define MAXN 510

char sum[MAXH] = {0};

{

sum[0] = 1;

{

for(int j = H;j > weight[i] + 1;j--)

sum[j] = 1;

}
for(int i = H;i >= 0;i--)

if(sum[i])

return i;

}
int main()

{

FILE * f = fopen("diet.in", "r");

fscanf(f, "%d\n", &weight[i]);

fprintf(fout, "%d\n", solve());

}

Problem 9: Heat Wave [300 points] [Rob Kolstad (traditional), 2009]

/ \

/ / /|

\ / / |

| /

2 4 2

7 2 2

5 7 5

6 1 1

2 4 3

7 2 1
INPUT DETAILS:

1. 
   We first start at the departure town Ts where its distance is 0, and the rest of the towns are not reachable yet, i.e., the distances of all towns are infinite.
   
2. 
   Update distances of the neighbor towns of the current town (dist[i] = min{dist[i],dist[current]+mat[current][i]} - i is neighbor of current).
   
3. 
   Always choose the shortest unvisited town from the departure town (current = min_i{dist[i]} - where i is unvisited).
   
4. 
   If the town is not the destination, return step 2.
   

In step 3, note that the shortest unvisited town has to be a neighbor of one of the explored towns since initially all towns are unreachable, later they become reachable when a neighbor town is visited in step 2. The algorithm with adjacency matrix requires O(T^2) running time since each node is visited once and all the neighbors of each node is explored using an adjacency matrix. Memory complexity is also O(T^2) since it requires adjacency matrix. The time and memory complexity can be reduced to O(C + T log T) by using a priority queue and an adjacency list however we don't need in this question.

Below is Rob Kolstad's solution:
#include
#define MAXN 2500

#define INF 1000000000

int dist[MAXN];

bool used[MAXN];
void readFile(char *inpFile) {

ifstream f(inpFile);

int a, b, c, d;
f >> T >> c >> Ts >> Te;

Ts--;

for (int i = 0; i < c; i++) {

f >> a >> b >> d;

mat[--a][--b] = mat[b][a] = d;

}

f.close ();

void solve () {

/* initialize the distance list of the towns */

for (int i = 0; i < T; i++)

dist[i] = INF;

dist[Ts] = 0; /* start from the departure town with 0 distance */

/* choose the shortest path from the list among unexplored towns */

int min = -1;

for (int i = 0; i < T; i++)

if (!used[i] && (min<0 || dist[min] > dist[i]))

min = i;
used[min] = true;

if (min == Te) /* done if destination town */

break;
/* update path */

for (int i = 0; i < T; i++)

if (mat[min][i] && dist[i] > dist[min] + mat[min][i])

dist[i] = dist[min] + mat[min][i];

}

}

readFile ("heatwv.in");

solve ();

ofstream f ("heatwv.out);

f << dist[Te] << "\n";

f.close ();

return 0;

}

Следва реализация на алгоритъма на Dijsktra със сложност O(C + T log T), която лесно може да се пpигоди за решение на дадената задача:

#include

#include

#include

using namespace std;

#define MP(x, y) make_pair((x), (y))

bool vis[MAX];

vector
> edges[MAX];
void printPath(int s, int j)

{

if (parent[j] != s)

printf("%d ", j + 1);

}
void printResult(int s)

{

for (int i = 0; i < E; i++)

if (dist[i] != INT_MAX && i != s)

{

printf("%d -> %d (%d): ", s + 1, i + 1, dist[i]);

printPath(s, i);

printf("\n");

}

}

{

freopen("dijikstra.in", "r", stdin);

scanf("%d %d", &E, &V);

for(int i = 0;i < V;i++)

{

scanf("%d %d %d", &u, &v, &c);

//edges[v].push_back(MP(u, c)); //if the graph is b-directional

}

}
void dijkstra(int s)

int i, u, v, w;

parent[s] = -1;

pq.push(MP(-dist[s], s));

{

u = pq.top().second;

if (vis[u])

continue;
vis[u] = true;

for(i = 0; i < edges[u].size(); i++)

{

v = edges[u][i].first;

{

dist[v] = dist[u] + w;

pq.push(MP(-dist[v], v));

}

}

}

{

for(int i = 0;i < E;i++)

dist[i] = INT_MAX;

vis[i] = false;

}

}

{

int startV = 5;

init();

printResult(startV);