Ferramentas de Utilizador
inf05504:2012-2-trabalhos
Diferenças
Esta página mostra as diferenças entre as duas revisões da página.
| Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
|
inf05504:2012-2-trabalhos [2012/12/06 17:04] marcus [Trabalho 4 (Emparelhamentos)] |
inf05504:2012-2-trabalhos [2013/01/13 09:01] (Actual) marcus [Entregas] |
||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| ==== Entregas ==== | ==== Entregas ==== | ||
| - | Atualizado: 02/10/2012 | + | Atualizado: 13/01/2012 |
| ^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | ^ No. ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^ | ||
| | 118489 | - | - | - | - | - | | | 118489 | - | - | - | - | - | | ||
| - | | 136830 | - | - | - | - | - | | + | | 136830 | P | - | - | - | - | |
| - | | 150821 | - | - | - | - | - | | + | | 150821 | P | - | P | - | P | |
| - | | 152985 | - | - | - | - | - | | + | | 152985 | P | P | P | P | P | |
| - | | 159847 | P | - | - | - | - | | + | | 159847 | P | P | P | R | P | |
| - | | 160636 | P | - | - | - | - | | + | | 160636 | P | P | P | - | P | |
| - | | 173362 | P | - | - | - | - | | + | | 173362 | P | R | - | - | P | |
| | 180190 | - | - | - | - | - | | | 180190 | - | - | - | - | - | | ||
| | 181026 | - | - | - | - | - | | | 181026 | - | - | - | - | - | | ||
| Linha 200: | Linha 200: | ||
| /** | /** | ||
| * \file maxflow.cpp | * \file maxflow.cpp | ||
| - | * \author Marcus Ritt <mrpritt@inf.ufrgs.br> | + | * \author Marcus Ritt <mrpritt@inf.ufrgs.br> |
| * \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $ | * \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $ | ||
| - | * \date Time-stamp: <2009-03-23 17:52:25 ritt> | + | * \date Time-stamp: <2012-12-06 17:10:05 ritt> |
| * | * | ||
| * Read a maximum flow problem in DIMACS format and output the maximum flow. | * Read a maximum flow problem in DIMACS format and output the maximum flow. | ||
| Linha 213: | Linha 213: | ||
| #include <boost/graph/adjacency_list.hpp> | #include <boost/graph/adjacency_list.hpp> | ||
| #include <boost/graph/read_dimacs.hpp> | #include <boost/graph/read_dimacs.hpp> | ||
| - | #include <boost/graph/edmunds_karp_max_flow.hpp> | + | #include <boost/graph/edmonds_karp_max_flow.hpp> |
| + | #include <boost/graph/push_relabel_max_flow.hpp> | ||
| using namespace boost; | using namespace boost; | ||
| + | |||
| + | // graph element descriptors | ||
| + | typedef adjacency_list_traits<vecS,vecS,directedS>::vertex_descriptor DiNode; | ||
| + | typedef adjacency_list_traits<vecS,vecS,directedS>::edge_descriptor Edge; | ||
| // a directed graph with reverse edges | // a directed graph with reverse edges | ||
| struct VertexInformation {}; | struct VertexInformation {}; | ||
| - | struct EdgeInformation; | ||
| - | |||
| - | typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph; | ||
| - | typedef graph_traits<DiGraph>::edge_descriptor Edge; | ||
| - | typedef graph_traits<DiGraph>::vertex_descriptor DiNode; | ||
| - | |||
| typedef unsigned Capacity; | typedef unsigned Capacity; | ||
| struct EdgeInformation { | struct EdgeInformation { | ||
| Linha 231: | Linha 229: | ||
| Edge reverse_edge; | Edge reverse_edge; | ||
| }; | }; | ||
| + | |||
| + | typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph; | ||
| int main(int argc, char *argv[]) { | int main(int argc, char *argv[]) { | ||
| Linha 237: | Linha 237: | ||
| DiGraph g; | DiGraph g; | ||
| DiNode s,t; | DiNode s,t; | ||
| + | | ||
| read_dimacs_max_flow(g, | read_dimacs_max_flow(g, | ||
| get(&EdgeInformation::edge_capacity,g), | get(&EdgeInformation::edge_capacity,g), | ||
| get(&EdgeInformation::reverse_edge,g), | get(&EdgeInformation::reverse_edge,g), | ||
| s, t); | s, t); | ||
| + | | ||
| // (1) determine maximum flow | // (1) determine maximum flow | ||
| - | cout << edmonds_karp_max_flow(g, s, t, | + | cout << push_relabel_max_flow(g, s, t, |
| capacity_map(get(&EdgeInformation::edge_capacity,g)). | capacity_map(get(&EdgeInformation::edge_capacity,g)). | ||
| residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)). | residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)). | ||
inf05504/2012-2-trabalhos.1354820695.txt.gz · Esta página foi modificada pela última vez em: 2012/12/06 17:04 por marcus
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
