fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. std::vector<int> matching;
  7. std::vector<char> visited;
  8.  
  9. bool try_kuhn (int v, std::vector <std::vector<int>> &graph) {
  10. 	if (visited[v]) {
  11.         return false;
  12.     }
  13. 	visited[v] = true;
  14. 	for (int i = 0; i < graph[v].size(); ++i) {
  15. 		int to = graph[v][i];
  16. 		if (matching[to] == -1 || try_kuhn (matching[to], graph)) {
  17. 			matching[to] = v;
  18. 			return true;
  19. 		}
  20. 	}
  21. 	return false;
  22. }
  23.  
  24. int main() {
  25.     int n, m, e;
  26.     std::cin >> n >> m >> e;
  27.     std::vector<std::pair<int, int>> weights_n(n);
  28.     std::vector<std::pair<int, int>> weights_m(m);
  29.     std::vector<int> edges;
  30.     std::vector <std::vector<int>> graph_n(n);
  31.     std::vector <std::vector<int>> graph_m(m);
  32.     std::vector <std::vector<int>> edges_matching(n);
  33.     std::vector<int> vertices_n(n);
  34.     std::vector<int> vertices_m(m);
  35.     for (int i = 0; i < n; ++i){
  36.         std::cin >> weights_n[i].first;
  37.         weights_n[i].second = i;
  38.         edges_matching[i].assign(m, 0);
  39.     }
  40.     for (int i = 0; i < m; ++i){
  41.         std::cin >> weights_m[i].first;
  42.         weights_m[i].second = i;
  43.     }
  44.     std::sort(weights_n.begin(), weights_n.begin() + weights_n.size(), std::greater<>());
  45.     std::sort(weights_m.begin(), weights_m.begin() + weights_m.size(), std::greater<>());
  46.     for (int i = 0; i < n; ++i) {
  47.         vertices_n[weights_n[i].second] = i;
  48.     }
  49.     for (int i = 0; i < m; ++i) {
  50.         vertices_m[weights_m[i].second] = i;
  51.     }
  52.     for (int i = 0; i < e; ++i){
  53.         int u, v;
  54.         std::cin >> u >> v;
  55.         edges_matching[u - 1][v - 1] = i + 1;
  56.         graph_n[vertices_n[u - 1]].push_back(v - 1);
  57.         graph_m[vertices_m[v - 1]].push_back(u - 1);
  58.     }
  59. 	matching.assign(m, -1);
  60. 	for (int v = 0; v < n; ++v) {
  61. 		visited.assign (n, false);
  62. 		try_kuhn (v, graph_n);
  63. 	}
  64. 	std::set<int> used_edges;
  65.     for (int i = 0; i < m; ++i){
  66.         if (matching[i] != -1) {
  67.             used_edges.insert(edges_matching[weights_n[matching[i]].second][i]);
  68.         }
  69.     }
  70.     matching.assign(n, -1);
  71.     for (int v = 0; v < m; ++v) {
  72.         visited.assign (m, false);
  73.         try_kuhn (v, graph_m);
  74.     }
  75.     std::vector<int> ret;
  76.     int weight = 0;
  77.     for (int i = 0; i < n; ++i){
  78.         if (matching[i] != -1) {
  79.             if (used_edges.count(edges_matching[i][weights_m[matching[i]].second])){
  80.                 ret.push_back(edges_matching[i][weights_m[matching[i]].second]);
  81.                 weight += weights_n[vertices_n[i]].first + weights_m[matching[i]].first;
  82.             }
  83.         }
  84.     }
  85.     std::cout << weight << "\n" << ret.size() << "\n";
  86.     for (int i = 0; i < ret.size(); ++i){
  87.         std::cout << ret[i] << " ";
  88.     }
  89.  
  90. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:1:10: fatal error: iostream: No such file or directory
 #include <iostream>
          ^~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/02zmMt
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!