#include using namespace std; const int MAXBUILDINGS = 40; const int MAXEDGES = 800; bool conns[MAXBUILDINGS][MAXBUILDINGS]; int vals[MAXBUILDINGS]; int bestCost; struct edge { int i, j; int cost; bool used; } edges[MAXEDGES]; bool best[MAXEDGES]; int visit(int v, int prev, int num, int n, bool& biConn) // // standard modified DFS method to check for biconnectivity // { int min; vals[v] = num; min = num; for(int i=0; i vals[v]) { biConn = false; return -1; } } else if (i != prev && vals[i] < min) min = vals[i]; } } return min; } bool biConnected(int n) /* * check if graph is biconnected */ { int j, k; for(k=1; k 0 || !biConn) return false; } } // j++; // for(;j 0) // not enough edges to be biconnected yet bestBiConn(e+1, maxedges, minedges, cost, n); else { if (biConnected(n)) { bestCost = cost; for(int k=0; k maxVal) { maxVal = edges[i].cost; e = i; } } return e; } void getEstimate(int n, int m) // // get an estimate of the min cost by removeing each edge, largest to // smallest: // if removal still results in biconnected graph // then discard edge // else use it in final solution // { for(int k=0; k> n >> m; int ncases = 0; while (n != 0) { ncases++; for(i=0; i> i >> j; edges[k].i = i-1; edges[k].j = j-1; cin >> edges[k].cost; bestCost += edges[k].cost; edges[k].used = false; // initializations for getEstimate conns[j-1][i-1] = conns[i-1][j-1] = true; } if (!biConnected(n)) cout << "There is no reliable net possible for test case " << ncases << "." << endl; else { getEstimate(n, m); // get estimate of lowest cost... bestCost++; // .. and make sure bestBiConn can // at least find this solution // initialize for bestBiConn by // removing all edges from graph for(i=0; i> n >> m; } return 0; }