fork download
copy 
  1. //84104971101048411497 - Can you guess what does this mean?
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef complex<double> point;
  8. #define mapii map<int, int>
  9. #define debug(a) cout << #a << ": " << a << endl
  10. #define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
  11. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  12. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  13. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
  14. #define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
  15. #define ii pair<int, int>
  16. #define iii pair<int, ii>
  17. #define ff first
  18. #define ss second
  19. #define mp make_pair
  20. #define pb push_back
  21. #define maxN 105
  22. #define oo 1000000007
  23. #define sz(a) (int)a.size()
  24.  
  25. const double PI = acos(-1.0);
  26.  
  27. double fRand(double fMin, double fMax)
  28. {
  29.     double f = (double)rand() / RAND_MAX;
  30.     return fMin + f * (fMax - fMin);
  31. }
  32.  
  33. template <class T>
  34. T min(T a, T b, T c) {
  35.     return min(a, min(b, c));
  36. }
  37.  
  38. template <class T>
  39. T max(T a, T b, T c) {
  40.     return max(a, max(b, c));
  41. }
  42.  
  43. struct Edge {
  44.     int v, cap, f, rev;
  45. };
  46.  
  47. struct MaxFlow {
  48.     vector<vector<Edge> > g;
  49.     int n;
  50.  
  51.     MaxFlow(int n): n(n) {
  52.         g.assign(n, vector<Edge>());
  53.     }
  54.  
  55.     void addEdge(int u, int v, int cap) {
  56.         g[u].pb({v, cap, 0, sz(g[v])});
  57.         g[v].pb({u, cap, 0, sz(g[u])-1});
  58.     }
  59.  
  60.     void BFS(int s, int t, vector<int> &pNode, vector<int> &pEdge, vector<int> &delta) {
  61.         vector<bool> visited(n, false);
  62.         delta.assign(n, 0);
  63.         delta[s] = oo;
  64.         visited[s] = true;
  65.  
  66.         queue<int> q;
  67.         q.push(s);
  68.         while (!q.empty()) {
  69.             int u = q.front(); q.pop();
  70.             fto(i, 0, sz(g[u])-1) {
  71.                 int v = g[u][i].v, nflow = g[u][i].cap - g[u][i].f;
  72.                 if (visited[v] || nflow == 0) continue;
  73.  
  74.                 visited[v] = true;
  75.                 delta[v] = min(delta[u], nflow);
  76.                 pNode[v] = u;
  77.                 pEdge[v] = i;
  78.                 q.push(v);
  79.             }
  80.         }
  81.     }
  82.  
  83.     int getFlow(int s, int t, int maxF) {
  84.         fto(u, 0, n-1) {
  85.             fto(i, 0, sz(g[u])-1) g[u][i].f = 0;
  86.         }
  87.         vector<int> pNode(n);
  88.         vector<int> pEdge(n);
  89.         vector<int> delta(n);
  90.         int flow = 0;
  91.  
  92.         while (true) {
  93.             BFS(s, t, pNode, pEdge, delta);
  94.             if (delta[t] == 0) break;
  95.             flow += delta[t];
  96.             if (flow >= maxF) break;
  97.  
  98.             for(int v = t; v != s; v = pNode[v]) {
  99.                 int u = pNode[v], i = pEdge[v];
  100.                 g[u][i].f += delta[t];
  101.                 g[v][g[u][i].rev].f -= delta[t];
  102.             }
  103.         }
  104.  
  105.         return flow;
  106.     }
  107. };
  108.  
  109. int n, m, c[maxN][maxN];
  110.  
  111. void Solve() {
  112.     MaxFlow g(n);
  113.  
  114.     int maxF = (n == 0) ? 0 : oo;
  115.     fto(u, 0, n-1) {
  116.         int deg = 0;
  117.         fto(v, 0, n-1) {
  118.             deg += c[u][v];
  119.             if (v > u && c[u][v]) g.addEdge(u, v, c[u][v]);
  120.         }
  121.         maxF = min(maxF, deg);
  122.     }
  123.  
  124.     fto(u, 0, n-1) {
  125.         fto(v, u+1, n-1) {
  126.             int x = g.getFlow(u, v, maxF);
  127.             maxF = min(maxF, x);
  128.         }
  129.     }
  130.  
  131.     printf("%d\n", maxF);
  132.     memset(c, 0, sizeof c);
  133. }
  134.  
  135. int toNum(string s) {
  136.     stringstream ss(s);
  137.     int x; ss >> x;
  138.     return x;
  139. }
  140.  
  141. void read(int &u, int &v) {
  142.     string s; cin >> s;
  143.     int p = s.find(",");
  144.     u = toNum(s.substr(1, p-1)); v = toNum(s.substr(p+1, sz(s)-p-2));
  145. }
  146.  
  147. int main () {
  148.     while (scanf("%d%d", &n, &m) != EOF) {
  149.         fto(i, 1, m) {
  150.             int u, v;
  151.             read(u, v);
  152.             ++c[u][v]; ++c[v][u];
  153.         }
  154.         Solve();
  155.     }
  156.  
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0s 15288KB
comments (?)
stdin
copy 
0 0
2 1 (0,1)
2 0
5 8 (0,1) (1,3) (2,3) (0,2) (0,1) (2,3) (2,4) (2,4)
stdout
copy 
0
1
0
2
https://ideone.com/4WGFxW
SEERC 2011 Problem B
language:
C++14 (gcc 8.3)
created:
7 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!