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

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

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

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

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

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

   Пример решения на 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;
}