A2.

/* * 可以把源问题转化成一个在PERT图上求关键路径的问题。 * 首先，每个格子在图上对应一个点，总共有n*n个点。从每个点向 * 它可以到达的点引一条有向边，边权为有向边的起始点对应的格子的 * 钱数。总的边数规模为O(k*n*n)。另外新建 * 一个汇点，所有出度为0的点向这个汇点引一条边。如此可以 * 构造出一个多源单汇的有向图。首先，把多余的源去掉。为此做一个 * 从(0,0)点开始的可达性检测。把不可达的节点删掉。这时我们得到一个 * PERT图。求从源到汇的最长路径，也就是关键路径。求关键路径首先做一次 * 拓扑排序，然后按照排序的结果分别计算源到每个点的关键路径。 * 建立图的复杂度为O(k*n*n),可达性检测的复杂度为O(n*n*k)。求关键路径 * 的复杂度也是O(k*n*n)。所以总的时间复杂度为O(k*n*n). */ #include "pertgraph.h" typedef graph<Node, Edge> Graph; void main(int argc, char** argv) { if (argc != 2) return; ifstream fin(argv[1]); int test_count, n, k; fin >> test_count; for (int i = 0; i < test_count; i++) { fin >> n; fin >> k; int * matrix = new int[n*n]; for (int j = 0; j < n*n; j++) fin >> matrix[j]; PERTGraph g(matrix, n, k); cout<<g.Pert()<<endl; } }

//////////////////////////////////////////////////////////////////////////////

// PERTGraph.cpp: implementation of the PERTGraph class. // ////////////////////////////////////////////////////////////////////// #include "PERTGraph.h" #define for if(0);else for ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// PERTGraph::PERTGraph(int* matrix, int _n, int _k):n(_n), k(_k) { BuildGraph(matrix, _n, _k); } PERTGraph::~PERTGraph() { } void PERTGraph::BuildGraph(int *matrix, int _n, int _k) { if (_k > _n-1) _k = _n-1; Node node; memset(&node, 0, sizeof(node)); for (int i = 0; i < _n*_n; i++) { AddNode(node); } for (int i = 0; i < _n; i++) // row { for (int j =0; j < _n; j++) //column { for (int l = 1; l <= _k; l++) { if ( j + l < _n) { if (matrix[i*_n+j] < matrix[i*_n+j+l]) { Edge edge; edge.node_index.first = i*_n+j; edge.node_index.second = i*_n+j+l; edge.weight = matrix[i*_n+j]; AddEdge(edge); } else if (matrix[i*_n+j] > matrix[i*_n+j+l]) { Edge edge; edge.node_index.first = i*_n+j+l; edge.node_index.second = i*_n+j; edge.weight = matrix[i*_n+j+l]; AddEdge(edge); } } if (i + l < _n) { if (matrix[i*_n+j] < matrix[(i+l)*_n+j]) { Edge edge; edge.node_index.first = i*_n+j; edge.node_index.second = (i+l)*_n+j; edge.weight = matrix[i*_n+j]; AddEdge(edge); } else if (matrix[i*_n+j] > matrix[(i+l)*_n+j]) { Edge edge; edge.node_index.first = (i+l)*_n+j; edge.node_index.second = i*_n+j; edge.weight = matrix[(i+l)*n+j]; AddEdge(edge); } } } } } AddNode(node); //index = n*n for (int i = 0; i < _n*_n; i++) if (nodes[i].out_degree == 0) { Edge edge; edge.node_index.first = i; edge.node_index.second = _n*_n; edge.weight = matrix[i]; AddEdge(edge); } } int PERTGraph::Pert() { //先做一个可达性分析，把无关的节点去掉。然后作一个拓扑排序。最后 vector<bool> tmp(nodes.size(), false); stack<int> node_stack; node_stack.push(0); tmp[0] = true; while(!node_stack.empty()) { int index = node_stack.top(); node_stack.pop(); for (int i = 0; i < out_links[index].size(); i++) { int edge_index = out_links[index][i]; if (!edges[edge_index].deleted) { int other_end = edges[edge_index].node_index.second; if (!tmp[other_end]) { tmp[other_end] = true; node_stack.push(other_end); } } } } for (int i = 0; i < tmp.size(); i++) { if (!tmp[i]) { DeleteNode(i); } } vector<int> index_vector; topological_sort(index_vector); // for (int i = 0; i < index_vector.size(); i++) // cout << index_vector[i]<<" "; // cout <<endl; // do pert evaluate vector<int> values(nodes.size(), 0); for (int i = 1; i < index_vector.size(); i++) { for (int j = 0; j < in_links[index_vector[i]].size(); j++) { int in_edge = in_links[index_vector[i]][j]; if (!edges[in_edge].deleted) { int in_node = edges[in_edge].node_index.first; values[index_vector[i]] = __max(values[index_vector[i]], values[in_node] + edges[in_edge].weight); } } } // for (int i = 0; i < values.size(); i++) // cout << values[i]<<" "; // cout <<endl; return values[values.size()-1]; } void PERTGraph::topological_sort(vector<int>& index_vector) { vector<int> in_degrees(nodes.size()); for (int i = 0; i < in_degrees.size(); i++) in_degrees[i] = nodes[i].in_degree; int node_i = 0; stack<int> node_stack; node_stack.push(0); while(!node_stack.empty()) { int index = node_stack.top(); index_vector.push_back(index); node_stack.pop(); for (int i = 0; i < out_links[index].size(); i++) { int edge_index = out_links[index][i]; if (!edges[edge_index].deleted) { int other_end = edges[edge_index].node_index.second; in_degrees[other_end] --; if (in_degrees[other_end] == 0) node_stack.push(other_end); } } } }

//////////////////////////////////////////////////////////////////////////////

//incident_graph.h #ifndef INCIDENT_GRAPH_H #define INCIDENT_GRAPH_H #include "stl.h" #define for if(0);else for class Edge{ public: pair<int, int> node_index; int weight; bool deleted; Edge():deleted(false), weight(0){} }; class Node{ public: int in_degree; int out_degree; bool deleted; Node():deleted(false), in_degree(0), out_degree(0){} }; template<typename NodeType, typename EdgeType> class graph { public: vector<NodeType> nodes;//set of nodes vector<EdgeType> edges;//set of edges vector<vector<int> > in_links; //in edge tables of nodes; vector<vector<int> > out_links; // out edge tables of nodes; public: graph(){}; virtual ~graph(){ Clear();} void Clear() { nodes.clear(); edges.clear(); in_links.clear();out_links.clear();} int NodeNum() { return nodes.size();} int EdgeNum() { return edges.size();} int FindNode(const NodeType& node) { std::vector<NodeType>::iterator it; it = std::find(nodes.begin(), nodes.end(), node); if (it == nodes.end() || (*it).deleted) return -1; return (it - nodes.begin()); } int AddNode(const NodeType& node){ int index = nodes.size(); nodes.push_back(node); vector<int> t; in_links.push_back(t); out_links.push_back(t); return index; } bool DeleteNode(int i) // deleted the { nodes[i].deleted = true; for (int k = 0; k < in_links[i].size(); k++) { DeleteEdge(in_links[i][k]); } for (int k = 0; k < out_links[i].size(); k++) { DeleteEdge(out_links[i][k]); } return true; } int FindEdge(const EdgeType& edge) { int s = links[edge.node_index.first].size(); for (int i = 0; i < s; i++) { const EdgeType& found = edge[links[edge.node_index.first][i]]; if (!found.deleted && (found.node_index.first == edge.node_index.first && found.node_index.first == edge.node_index.second || found.node_index.second == edge.node_index.first && found.node_index.first == edge.node_index.second)) return i; } return -1; } int AddEdge(const EdgeType& edge) { int size = edges.size(); edges.push_back(edge); nodes[edge.node_index.first].out_degree ++; nodes[edge.node_index.second].in_degree ++; out_links[edge.node_index.first].push_back(size); in_links[edge.node_index.second].push_back(size); return size; } bool DeleteEdge(int index) { EdgeType& edge = edges[index]; if (! edge.deleted) { edge.deleted = true; nodes[edge.node_index.first].out_degree --; nodes[edge.node_index.second].in_degree --; } return true; } virtual ostream & Dump(ostream & o); friend ostream & operator <<(ostream& o, graph<NodeType, EdgeType>& g); }; /* Dumping the graph to an ostream. NOTICE: this method is a virtual method. Parameter: the ostream to dump to. */ template<typename NodeType, typename EdgeType> ostream& graph<NodeType, EdgeType>::Dump(ostream& o) { for (int i = 0; i < edges.size(); i++) { if (!edges[i].deleted) o << "<" << edges[i].node_index.first << "," << edges[i].node_index.second << ">" <<endl; } /* int n = NodeNum(); o<<"there are "<<n<<" nodes:"<<endl; if (n <= 10) for(int i=0; i<n; i++) o << "<" << nodes[i] << ">"<<endl; int m = EdgeNum(); o<<"there are "<<m<<" edges:" << endl; if (m <= 10) for(int i = 0; i < n; i++) { int k = links[i].size(); for(int j = 0; j < k; j++) o << "{" << edges[links[i][j].edge] << "}: " << i << ":<" << nodes[i] < < "> -> " << links[i][j].endnode << ":<"<< nodes[links[i][j].endnode] < < ">" << endl; } */ return o; } /* Overload the operator '<<' for class graph to make it can be more clearly used. Parameter: the ostream to dump to, the graph to be dumped. */ template<typename NodeType, typename EdgeType> ostream& operator << (ostream& o, graph<NodeType, EdgeType> &g){return g.Dump(o);} #endif // GRAPH_H

/////////////////////////////////////////////////////////////////////////////////

// PERTGraph.h: interface for the PERTGraph class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_PERTGRAPH_H__6924DBA6_1D89_44FC_96BE_D5D6D583D0AF__INCLUDED_) #define AFX_PERTGRAPH_H__6924DBA6_1D89_44FC_96BE_D5D6D583D0AF__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include "incident_graph.h" class PERTGraph : public graph<Node, Edge> { public: void BuildGraph(int* matrix, int _n, int _k); PERTGraph(int* matrix, int n, int k); int Pert(); void topological_sort(vector<int>& index_vector); virtual ~PERTGraph(); private: int n; int k; }; #endif // !defined(AFX_PERTGRAPH_H__6924DBA6_1D89_44FC_96BE_D5D6D583D0AF__INCLUDED_)

//////////////////////////////////////////////////////////////////////

//stl.h #ifndef STL_H #define STL_H #include <vector> #include <iostream> #include <fstream> #include <stack> using namespace std; #endif;

A3.

/* * 求割点和块的程序 */ /* * Ploblem A3. 根据题目的要求，照相机安放的地点应为图的割点。 * 找图的割点用深度优先的搜索方法，对于深度优先搜索树的根结点， * 如果其子树多于1，则根结点为割点；对于非根节点，只要其子树的每个节点没有回退边。 * 复杂度为深度优先搜索图的复杂度，每条边遍历一次，复杂度为O(m).m为边数 */ #pragma warning (disable:4786) #include <iostream> #include <vector> #include <stack> #include <string> #include <fstream> #include <map> #include "linkmatrixgraph.h" #define for if(0);else for using namespace std; void main(int argc, char** argv) { if (argc != 2) return; ifstream fin(argv[1]); map<string, int> names_map; vector<string> names_vector; int mapNo = 0; while(1) { mapNo ++; names_map.clear(); names_vector.clear(); int node_num; fin>>node_num; if (node_num == 0) break; names_vector.resize(node_num); for (int i = 0; i < node_num; i++) { string name; fin>>name; names_vector[i] = name; names_map[name] = i; } LinkMatrixGraph graph(node_num); int edge_num; fin>>edge_num; for (int i = 0; i < edge_num; i++) { string name1; string name2; fin>>name1>>name2; graph.addEdge(names_map[name1], names_map[name2]); } vector<int> nodes; graph.biconnect(nodes); printf("City map #%d: %d camera(s) found\n", mapNo, nodes.size()); for (int i = 0; i < nodes.size(); i++) { cout<<names_vector[nodes[i]]<<endl; } } }

// LinkMatrixGraph.cpp: implementation of the LinkMatrixGraph class. // ////////////////////////////////////////////////////////////////////// #include "LinkMatrixGraph.h" #define for if(0); else for ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// LinkMatrixGraph::LinkMatrixGraph(size_t vertex_size) { init(vertex_size); } LinkMatrixGraph::~LinkMatrixGraph() { clear(); } bool LinkMatrixGraph::init(size_t vertex_size) { m_nVertexSize = vertex_size; m_pMatrix = new bool*[vertex_size]; for (int i = 0; i < vertex_size; i++) { m_pMatrix[i] = new bool[vertex_size]; memset(m_pMatrix[i], 0, vertex_size*sizeof(bool)); } return true; } void LinkMatrixGraph::clear() { for (int i = 0; i < m_nVertexSize; i++) { delete [] m_pMatrix[i]; } delete[] m_pMatrix; } void LinkMatrixGraph::DFS(int v) { for (int u = 0; u < m_nVertexSize; u++) { if (m_pMatrix[u][v]) //有边，则分析 { if (dfn[u] == -1) //首次被访问 { visit_index++; dfn[u] = visit_index; low[u] = visit_index; DFS(u); low[v] = __min(low[v], low[u]); if (low[u] >= dfn[v]) { //从v的后代不会追溯到v的祖先，v是割点 if (v != root) { cut_points[v] = true; } else { nSubTreeOfRoot++; } } } else //已经被访问过，则这条是后向边 { low[v] = __min(low[v], dfn[u]); } } } } void LinkMatrixGraph::init_DFS() { root = 0; visit_index = 0; dfn.clear(); low.clear(); visited.clear(); cut_points.clear(); dfn.resize(m_nVertexSize, -1); low.resize(m_nVertexSize, -1); visit_index = 0; visited.resize(m_nVertexSize, false); cut_points.resize(m_nVertexSize, false); nSubTreeOfRoot = 0; visit_index ++; dfn[root] = visit_index; low[root] = visit_index; } void LinkMatrixGraph::biconnect(vector<int>& _cut_points) { init_DFS(); DFS(root); if (nSubTreeOfRoot > 1) cut_points[root] = true; _cut_points.clear(); for (int i = 0; i < m_nVertexSize; i++) { if (cut_points[i]) _cut_points.push_back(i); } // copy(cut_points.begin(), cut_points.end(), _cut_points.begin()); } void LinkMatrixGraph::addEdge(int u, int v) { m_pMatrix[u][v] = true; m_pMatrix[v][u] = true; }

// LinkMatrixGraph.h: interface for the LinkMatrixGraph class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_LINKMATRIXGRAPH_H__DDA6FDB9_B8BA_4F87_A6D0_C97B7FFA0CCA__INCLUDED_) #define AFX_LINKMATRIXGRAPH_H__DDA6FDB9_B8BA_4F87_A6D0_C97B7FFA0CCA__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #include <vector> using namespace std; class LinkMatrixGraph { public: void addEdge(int u, int v); /* * 调用biconnect，返回割点的序号在_cut_points里面 */ void biconnect(vector<int>& _cut_points); LinkMatrixGraph(size_t vertex_size); virtual ~LinkMatrixGraph(); private: size_t m_nVertexSize; bool ** m_pMatrix; /* * 初始化 */ bool init(size_t vertex_size); /* * 初始化深度优先搜索 */ void init_DFS(); /* * 深度优先搜索节点v */ void DFS(int v); void clear(); vector<int> dfn; vector<int> low; vector<bool> visited; int visit_index; vector<bool> cut_points; //割点集 int root; int nSubTreeOfRoot; }; #endif // !defined(AFX_LINKMATRIXGRAPH_H__DDA6FDB9_B8BA_4F87_A6D0_C97B7FFA0CCA__INCLUDED_)

A5.

/* * Problem A5, 新建一个数组保存每个时刻的用电总数。找出第一个超过用电量的 * 时刻。 */ #pragma warning (disable:4786) #include <iostream> #include <fstream> #include <string> #include <map> #include <assert.h> using namespace std; #define for if (0); else for void algorithm(const char* filename); void read_name(istream& fin, string& name); void main(int argc, char** argv) { if (argc == 2) algorithm(argv[1]); } void read_name(istream& fin, string& name) { while(fin.get() != (int)'['); int pos = 0; do { char c = fin.get(); if (c == ']'|| pos == name.size()-1) break; else name[pos++] = c; } while(1); name[pos] = '\0'; } void algorithm (const char* filename) { map<string, int> powers; ifstream fin(filename); int size; fin >> size; int * timeline = new int[32769]; for (int i = 0; i < size; i++) { string name(31, 0); read_name(fin, name); int power; fin>>power; powers[name] = power; int u = powers[name]; } while(1) { memset(timeline, 0, sizeof(int)*32769); int K; int P; fin >>K; if (fin.fail()) break; fin >>P; bool enough = true; int first_out = -1; int max_needed = 0; for (int i = 0; i < K; i++) { string name(31, 0); read_name(fin, name); int begin_time, end_time; fin>>begin_time>>end_time; int power = powers[name]; for (int j = begin_time; j <= end_time; j++) { timeline[j] += power; if (timeline[j] > max_needed) max_needed = timeline[j]; if (timeline[j] > P) { if (first_out == -1 || j < first_out) { enough = false; first_out = j; } } } } if (enough) { printf("The maximum power needed is %d Watts\n", max_needed); } else { printf("The power will be out at time %d because the power is %d Watts and overloaded\n", first_out, timeline[first_out]); } } delete [] timeline; }

此作品提交了完整的工程文件。强烈建议你下载其完整工程，在VC＋＋中阅读欣赏其代码。