codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_VERTICES 250 #define ADJ(v1, v2) adjacent[(v1) * num_vertices + (v2)] int num_test_cases; //<! Number of test cases int num_edges; //<! Number of edges int num_vertices; //<! Number of vertices int weights[MAX_VERTICES]; //<! Vertex weights int colors[MAX_VERTICES]; //<! Vertex colors int adjacent[MAX_VERTICES * MAX_VERTICES - 1]; //<! Flattened adjacency matrix int cur_clique[MAX_VERTICES]; //<! Current clique int cur_clique_size; //<! Size of the current clique int cur_clique_weight; //<! Weight of the current clique int best_clique_weight; //<! Weight of the best clique /*! * Expand each vertex of the given graph against the current clique. */ void expand(int *graph, int graph_size) { bool any_expanded = false; /* Loop through each vertex in the graph */ for(int i = 0; i < graph_size; i++) { /* See if it is expandable -- if it is adjacent to all vertices in the clique */ bool expandable = true; for(int j = 0; j < cur_clique_size; j++) { if(!ADJ(graph[i], cur_clique[j])) { expandable = false; break; } } if(expandable) { any_expanded = true; /* Add it to the current clique */ cur_clique[cur_clique_size++] = graph[i]; cur_clique_weight += weights[graph[i]]; /* Build a new graph of all vertices in this graph adjacent to it */ int *next_graph = malloc(graph_size * sizeof(int)); int next_graph_size = 0; for(int j = 0; j < graph_size; j++) { if(j != i && ADJ(graph[i], graph[j])) { next_graph[next_graph_size++] = graph[j]; } } /* Expand the next graph */ expand(next_graph, next_graph_size); /* Destroy the temporary graph */ free(next_graph); /* Remove it from the current clique */ cur_clique_size--; cur_clique_weight -= weights[graph[i]]; } } if(!any_expanded && cur_clique_weight > best_clique_weight) { best_clique_weight = cur_clique_weight; } } /*! * Find the maximum clique */ void max_clique() { /* Initialize */ best_clique_weight = 0; cur_clique_size = 0; cur_clique_weight = 0; /* Expand the full graph */ int * full_graph = malloc(num_vertices * sizeof(int)); for(int i = 0; i < num_vertices; i++) { full_graph[i] = i; } expand(full_graph, num_vertices); } int main(int argc, char **argv) { scanf("%d", &num_test_cases); for(int i = 0; i < num_test_cases; i++) { /* Reset data */ scanf("%d %d", &num_vertices, &num_edges); for(int j = 0; j < num_vertices * num_vertices - 1; j++) { adjacent[j] = 1; } memset(colors, 0, num_vertices); /* Read vertices */ for(int j = 0; j < num_vertices; j++) { scanf("%d", &weights[j]); } /* Read edges */ for(int j = 0; j < num_edges; j++) { int v1, v2; scanf("%d %d", &v1, &v2); ADJ(v1 - 1, v2 - 1) = 0; ADJ(v2 - 1, v1 - 1) = 0; } /* Do the work */ max_clique(); /* Show the results */ printf("%d\n", best_clique_weight); } return 0; }
Private
[
?
]
Run code
Submit