http://acm.pku.edu.cn/JudgeOnline/problem?id=1073
Код:
#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; }