fork download
copy 
  1. //Done by: K Ashwin
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9.  
  10. #define REP(i, a, b) \
  11. for (int i = int(a); i <= int(b); i++) // a to b, and variable i is local!
  12. #define TR(c, it) \
  13. for (auto it = (c).begin(); it != (c).end(); it++)
  14.  
  15. #define s(x) scanf("%d", &x)
  16. #define sl(x) scanf("%lld", &x)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define fi first
  20. #define se second
  21. #define set0(a) memset(a, 0, sizeof(a))
  22. #define setdp(a) memset(a, -1, sizeof(a))
  23. #define INF 2000000000
  24. #define MOD 1000000007
  25.  
  26. struct edge
  27. {
  28.     int a, b, cap, flow;
  29. };
  30.  
  31. vector <edge> e;
  32. vector <int> g[2005];
  33. vector <pii> p1, p2;
  34. int L[2005], ptr[2005], S, T, n, m;
  35.  
  36. void add_edge(int a, int b, int cap)
  37. {
  38.     edge e1 = {a, b, cap, 0};
  39.     edge e2 = {b, a, 0, 0};
  40.     g[a].pb((int)e.size());
  41.     e.pb(e1);
  42.     g[b].pb((int)e.size());
  43.     e.pb(e2);
  44.  
  45.     //cout << "edge " << a << " " << b << " " << cap << endl;
  46. }
  47.  
  48. bool bfs()
  49. {
  50.     queue <int> q;
  51.     int cur;
  52.  
  53.     set0(L);
  54.  
  55.     q.push(S);
  56.     L[S] = 1;
  57.  
  58.     while (!q.empty()) {
  59.         cur = q.front();
  60.         q.pop();
  61.  
  62.         //cout << "qu " << cur << endl;
  63.  
  64.         for (int i = 0; i < g[cur].size(); i++) {
  65.             int id = g[cur][i], to = e[id].b;
  66.  
  67.             if (!L[to] && e[id].flow < e[id].cap) {
  68.                 L[to] = L[cur] + 1;
  69.                 q.push(to);
  70.             }
  71.         }
  72.     }
  73.  
  74.     //cout << "bfs " << L[T] << endl;
  75.  
  76.     return L[T];
  77. }
  78.  
  79. int dfs(int cur, int flow)
  80. {
  81.     if (!flow)
  82.         return 0;
  83.  
  84.     if (cur == T)
  85.         return flow;
  86.  
  87.     for (; ptr[cur] < g[cur].size(); ptr[cur]++) {
  88.         int id = g[cur][ptr[cur]], to = e[id].b;
  89.  
  90.         if (L[to] != L[cur] + 1)
  91.             continue ;
  92.  
  93.         int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
  94.         if (pushed) {
  95.             e[id].flow += pushed;
  96.             e[id^1].flow -= pushed;
  97.  
  98.             return pushed;
  99.         }
  100.     }
  101.  
  102.     return 0;
  103. }
  104.  
  105. int dinic()
  106. {
  107.     int flow = 0, t1;
  108.  
  109.     while (bfs()) {
  110.         set0(ptr);
  111.  
  112.         while (t1 = dfs(S, INF))
  113.             flow += t1;
  114.     }
  115.  
  116.     //cout << "flow " << flow << endl;
  117.  
  118.     return flow;
  119. }
  120.  
  121. void mems()
  122. {
  123.     e.clear();
  124.     p1.clear();
  125.     p2.clear();
  126.     REP (i, 0, 2002) {
  127.         g[i].clear();
  128.     }
  129. }
  130.  
  131. int main()
  132. {
  133.     int t, x, y;
  134.  
  135.     cin >> t;
  136.  
  137.     while (t--) {
  138.         mems();
  139.  
  140.         cin >> n >> m;
  141.  
  142.         S = 0;
  143.         T = 2002;
  144.         REP (i, 1, n) {
  145.             s(x);
  146.             s(y);
  147.  
  148.             p1.pb(mp(x, y));
  149.         }
  150.  
  151.         REP (i, 1, m) {
  152.             s(x);
  153.             s(y);
  154.  
  155.             p2.pb(mp(x, y));
  156.         }
  157.  
  158.         REP (i, 1, n)
  159.             add_edge(S, i, 1);
  160.  
  161.         REP (i, 0, n - 1) {
  162.             REP (j, 0, m - 1) {
  163.                 if (p1[i].fi == p2[j].fi || p1[i].se == p2[j].se || abs(p1[i].fi - p2[j].fi) == abs(p1[i].se - p2[j].se))
  164.                     add_edge(i + 1, n + j + 1, 1);
  165.             }
  166.         }
  167.  
  168.         REP (i, 1, m)
  169.             add_edge(n + i, T, 1);
  170.  
  171.         cout << dinic() << endl;
  172.     }
  173.  
  174.     return 0;
  175. }
  176.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python2.7/py_compile.py", line 117, in compile
    raise py_exc
py_compile.PyCompileError:   File "prog.py", line 1
    //Done by: K Ashwin
     ^
SyntaxError: invalid syntax
stdout
copy 
Standard output is empty
https://ideone.com/wfCcEY
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
secret

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!