Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.44 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <ctime>
  9. #include <fstream>
  10. #include <iomanip>
  11. #include <iostream>
  12. #include <list>
  13. #include <map>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <stack>
  18. #include <string>
  19. #include <utility>
  20. #include <vector>
  21. using namespace std;
  22.  
  23. #define all(o) (o).begin(), (o).end()
  24. #define allr(o) (o).rbegin(), (o).rend()
  25. const int INF = 2147483647;
  26. typedef long long ll;
  27. typedef pair<int, int> ii;
  28. typedef vector<int> vi;
  29. typedef vector<ii> vii;
  30. typedef vector<vi> vvi;
  31. typedef vector<vii> vvii;
  32. template <class T> int size(T &x) { return x.size(); }
  33.  
  34. // assert or gtfo
  35.  
  36. struct flow_network {
  37.  
  38.     struct edge {
  39.         int u, v, cap;
  40.         edge *rev;
  41.         bool forward;
  42.         edge(int _u, int _v, int _cap, bool forw)
  43.             : u(_u), v(_v), cap(_cap), forward(forw) { }
  44.     };
  45.  
  46.     int n;
  47.     vector<vector<edge*> > adj;
  48.     flow_network(int _n) : n(_n), adj(_n) { }
  49.  
  50.     void add_edge(int u, int v, int cap) {
  51.         edge *e = new edge(u, v, cap, true);
  52.         edge *rev = new edge(v, u, 0, false);
  53.         e->rev = rev;
  54.         rev->rev = e;
  55.         adj[u].push_back(e);
  56.         adj[v].push_back(rev);
  57.     }
  58.  
  59.     int augment(int s, int t) {
  60.         vector<edge*> back(n, (edge*)0);
  61.         queue<int> Q;
  62.         Q.push(s);
  63.         back[s] = (edge*)1;
  64.         while (!Q.empty()) {
  65.             int u = Q.front(); Q.pop();
  66.             for (unsigned int i = 0; i < adj[u].size(); i++) {
  67.                 int v = adj[u][i]->v;
  68.                 if (back[v] == NULL && adj[u][i]->cap > 0) {
  69.                     back[v] = adj[u][i];
  70.                     Q.push(v);
  71.                 }
  72.             }
  73.         }
  74.  
  75.         if (back[t] == NULL)
  76.             return 0;
  77.  
  78.         stack<edge*> S;
  79.         S.push(back[t]);
  80.         int bneck = back[t]->cap;
  81.         while (S.top()->u != s) {
  82.             S.push(back[S.top()->u]);
  83.             bneck = min(bneck, S.top()->cap);
  84.         }
  85.  
  86.         while (!S.empty()) {
  87.             S.top()->cap -= bneck;
  88.             S.top()->rev->cap += bneck;
  89.             S.pop();
  90.         }
  91.  
  92.         return bneck;
  93.     }
  94.  
  95.     int max_flow(int source, int sink) {
  96.         int flow = 0;
  97.         while (true) {
  98.             int f = augment(source, sink);
  99.             if (f == 0) {
  100.                 break;
  101.             }
  102.  
  103.             flow += f;
  104.         }
  105.  
  106.         return flow;
  107.     }
  108. };
  109.  
  110. int main()
  111. {
  112.  
  113.     int n, m, x, y;
  114.     cin >> n >> m;
  115.  
  116.      int SOURCE = 0,
  117.         SINK = 1,
  118.         LEFT = 2,
  119.         RIGHT = LEFT + n,
  120.         CNT = (2 * n) + 2;
  121.  
  122.     flow_network flow(n * n + 2);
  123.  
  124.     for(int i = 0; i < m; i++)
  125.     {
  126.         cin >> x >> y;
  127.         flow.add_edge(LEFT + x, RIGHT + y, 1);
  128.     }
  129.  
  130.     for (int i = 0; i < n; i++) {
  131.         flow.add_edge(SOURCE, LEFT + i, 1);
  132.     }
  133.  
  134.     for (int i = 0; i < n; i++) {
  135.         flow.add_edge(RIGHT + i, SINK, 1);
  136.     }
  137.  
  138.     int mx = flow.max_flow(SOURCE, SINK);
  139.     if(mx > n)
  140.     {
  141.         cout << "Impossible";
  142.         return 0;
  143.     }
  144.     for(int u = 0; u < n; u++)
  145.     {
  146.         for(unsigned int i = 0; i < flow.adj[LEFT + u].size(); i++)
  147.         {
  148.             if(flow.adj[LEFT + u][i]->forward && flow.adj[LEFT + u][i]->rev->cap != 0)
  149.             {
  150.                 cout << flow.adj[LEFT + u][i]->v - RIGHT << endl;
  151.             }
  152.         }
  153.     }
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement