Отримання знань

дистанційна підтримка освіти школярів


Мемориальная программа Вилли
http://acm.pku.edu.cn/JudgeOnline/problem?id=1073

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
#include "list"
#include "queue"
#include "stack"
using namespace std;

struct linkpair {
int index, y;
linkpair() {}
linkpair(int a, int b) { index = a; y = b; }
};
struct waterpipe {
int x, y, h;
list < linkpair > adj; /* adjacency list */
};

bool paircompare(linkpair a, linkpair b) {
if ( a.y > b.y )
return true;
else if ( a.y < b.y )
return false;
return false;
}

int max(int a, int b) {
return ( a > b ? a : b);
}

int height[200];
int path[200];

bool dfs(bool end_in_path, int start, int end, int current_inflow, int target_level,
int npipes, waterpipe pipes[], int visited[], int depth) {
path[depth] = start;
visited[start] = 1; // base
height[start] = -1; // base case - sentinel for no next
for ( list < linkpair > ::iterator lit = pipes[start].adj.begin();
lit != pipes[start].adj.end(); lit++ ) {
if ( visited[lit -> index] == 1 )
continue; /* cycle */
/* ignore paths that need water higher than target */
/* if end seen in path, don't need to go higher. */
if ( end_in_path && lit -> y < target_level )
continue;

int outflow = lit -> y;
/* if outflow higher than current inflow,
and outflow is higher than bottom of pipe */
if ( outflow < current_inflow &&
outflow < pipes[start].y + pipes[start].h ) {
height[start] = lit -> y;
if ( (dfs(start == end || end_in_path, lit -> index, end, 201, target_level,
npipes, pipes, visited, depth+1)) >= 0 )
return true;
} else {
height[start] = min(current_inflow, target_level);
if ( (dfs(start == end || end_in_path, lit -> index, end, height[start], target_level,
npipes, pipes, visited, depth+1)) >= 0 )
return true;
}
}
visited[start] = 2; // base
if ( end_in_path ) {
height[depth] = target_level;
for ( int j = 1; j <= depth; j++ )
for ( int i = 0; i < j; i++ )
if ( height[path[i]] > height[path[j]] )
height[path[i]] = height[path[j]];
return true;
}
return false;
}

int main(void) {
int cases, npipes, nlinks;
cin >> cases;
while ( cases-- > 0 ) {
cin >> npipes;
waterpipe pipes[npipes];
for ( int i = 0; i < npipes; i++ )
cin >> pipes[i].x >> pipes[i].y >> pipes[i].h;

/* build graph of pipes */
cin >> nlinks;
for ( int i = 0; i < nlinks; i++ ) {
int x, y, l, from = -1, to = -1;
cin >> x >> y >> l;
/* find from endpoint of link */
for ( int j = 0; j < npipes; j++ ) {
if ( pipes[j].x + 1 == x &&
y >= pipes[j].y &&
y <= pipes[j].y + pipes[j].h ) {
from = j;
break;
}
}
/* find to endpoint of link */
for ( int j = 0; j < npipes; j++ ) {
if ( pipes[j].x == x + l &&
y >= pipes[j].y &&
y <= pipes[j].y + pipes[j].h ) {
to = j;
break;
}
}
pipes[from].adj.push_back(linkpair(to, y));
pipes[to].adj.push_back(linkpair(from, y));
}

/* sort adjacency lists lowest-junction first */
for ( int i = 0; i < npipes; i++ )
pipes[i].adj.sort(paircompare);

/* read in target pipe/level */
int target_pipe, target_level;
cin >> target_pipe >> target_level;
target_pipe--; /* adjust for target pipe start index */

int visited[npipes];
for ( int i = 0; i < npipes; i++ )
visited[i] = 0;

/* initialize height to -1s */
for ( int i = 0; i < npipes; i++ )
height[i] = -1;

/* !!!!!!dfs through lowest links first!!!!!! */
dfs(false, 0, target_pipe, 201 /* > max y */, target_level, npipes, pipes, visited, 0);

/* impossible if: cannot reach pipe, or level */
bool impossible = false;
if ( !visited[target_pipe] )
impossible = true;
/* if any reachable pipe has y > target, impossible */
for ( int i = 0; !impossible && i < npipes; i++ )
if ( visited[i] && pipes[i].y >= height[0] )
impossible = true;
/* if target is below target pipe, impossible
(above is caught by impossible check above) */
if ( target_level > pipes[target_pipe].y + pipes[target_pipe].h )
impossible = true;
if ( impossible ) {
cout << "No Solution" << endl;
continue;
}

/* possible */
int sum = 0;
for ( int i = 0; i < npipes; i++ )
if ( (visited[i] == 1 || visited[i] == 2) && height[i] >= 0 )
sum += max(0, pipes[i].h + pipes[i].y - height[i]);
cout << sum << endl;
}

return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)