chuka231's blog: cses

 int n, m;  
 Int adj[555][555];  
 Int oadj[555][555];  
 Int flow[555];  
 bool V[555];  
 int pa[555];  
 vector <pi> ans;  
 bool reachable() {  
      memset(V, false, sizeof V);  
      queue<int> Q;  
      Q.push(1); V[1] = 1;  
      while (!Q.empty()) {  
           int i = Q.front(); Q.pop();  
           RREP(j, n) if (adj[i][j] && !V[j]) {  
                V[j] = 1;  
                pa[j] = i;  
                Q.push(j);  
           }  
      }  
      return V[n];  
 }  
 void solve() {  
      cin >> n >> m;  
      RREP(i, n) RREP(j, n) adj[i][j] = oadj[i][j] = 0;  
      REP(i, m) {  
           Int a, b;  
           cin >> a >> b;  
           adj[a][b]++; adj[b][a]++;  
           oadj[a][b]++; oadj[b][a]++;  
      }  
      int v, u;  
      while (reachable()) {  
           Int flow = LINF;  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                flow = min(flow, adj[u][v]);  
           }  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                adj[u][v] -= flow;  
                adj[v][u] += flow;  
           }  
      }  
      reachable();  
      RREP(i, n) RREP(j, n) {  
           if (V[i] && !V[j] && oadj[i][j]) ans.push_back(pi(i, j));  
      }  
      cout << ans.size() << endl;  
      for (auto x : ans) cout << x.first << " " << x.second << endl;  
 }

Saturday, January 29, 2022

CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }