fork(1) download
copy 
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30. #define SZ(S) ((int) ((S).size()))
  31.  
  32. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  33. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  34. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  35.  
  36. const int INF = 1000000000;
  37.  
  38. struct Edge {
  39.     int a, b, cap, flow;
  40. };
  41.  
  42. struct MaxFlow {
  43.     int n, s, t;
  44.     vector<int> d, ptr, q;
  45.     vector< Edge > e;
  46.     vector< vector<int> > g;
  47.  
  48.     MaxFlow(int n) : n(n), d(n), ptr(n), g(n), q(n) {
  49.         e.clear();
  50.         REP(i,n) {
  51.             g[i].clear();
  52.             ptr[i] = 0;
  53.         }
  54.     }
  55.  
  56.     void addEdge(int a, int b, int cap) {
  57.         Edge e1 = { a, b, cap, 0 };
  58.         Edge e2 = { b, a, 0, 0 };
  59.         g[a].push_back( (int) e.size() );
  60.         e.push_back(e1);
  61.         g[b].push_back( (int) e.size() );
  62.         e.push_back(e2);
  63.     }
  64.     int getMaxFlow(int _s, int _t) {
  65.         s = _s; t = _t;
  66.         int flow = 0;
  67.         for (;;) {
  68.             if (!bfs()) break;
  69.             REP(i,n) ptr[i] = 0;
  70.             while (int pushed = dfs(s, INF))
  71.                 flow += pushed;
  72.         }
  73.         return flow;
  74.     }
  75.  
  76. private:
  77.     bool bfs() {
  78.         int qh = 0, qt = 0;
  79.         q[qt++] = s;
  80.         REP(i,n) d[i] = -1;
  81.         d[s] = 0;
  82.  
  83.         while (qh < qt && d[t] == -1) {
  84.             int v = q[qh++];
  85.             REP(i,g[v].size()) {
  86.                 int id = g[v][i], to = e[id].b;
  87.                 if (d[to] == -1 && e[id].flow < e[id].cap) {
  88.                     q[qt++] = to;
  89.                     d[to] = d[v] + 1;
  90.                 }
  91.             }
  92.         }
  93.         return d[t] != -1;
  94.     }
  95.  
  96.     int dfs (int v, int flow) {
  97.         if (!flow) return 0;
  98.         if (v == t) return flow;
  99.         for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
  100.             int id = g[v][ptr[v]],
  101.                 to = e[id].b;
  102.             if (d[to] != d[v] + 1) continue;
  103.             int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
  104.             if (pushed) {
  105.                 e[id].flow += pushed;
  106.                 e[id^1].flow -= pushed;
  107.                 return pushed;
  108.             }
  109.         }
  110.         return 0;
  111.     }
  112. };
  113.  
  114. const int MN = 111;
  115. const int MM = 10111;
  116. const int oo = 1000111000;
  117. int n, m, c[MN][MN];
  118. int eu[MM], ev[MM], ec[MM];
  119.  
  120. int main() {
  121.     ios :: sync_with_stdio(false); cin.tie(NULL);
  122.     cout << (fixed) << setprecision(6);
  123.     while (cin >> n >> m) {
  124.         FOR(i,1,n) FOR(j,1,n) c[i][j] = oo;
  125.         FOR(i,1,n) c[i][i] = 0;
  126.         FOR(i,1,m) {
  127.             int u, v, l; cin >> u >> v >> l;
  128.             ++u; ++v;
  129.             eu[i] = u; ev[i] = v; ec[i] = l;
  130.             c[u][v] = min(c[u][v], l);
  131.             c[v][u] = c[u][v];
  132.         }
  133.         FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
  134.  
  135.         if (c[1][n] == oo) {
  136.             cout << 0 << endl;
  137.             continue;
  138.         }
  139.  
  140.         MaxFlow flow(2*n);
  141.         FOR(i,1,n) {
  142.             int c = (i == 1 || i == n) ? oo : 1;
  143.             flow.addEdge(2*i-2, 2*i-1, c);
  144.         }
  145.         FOR(i,1,m) {
  146.             if (c[1][eu[i]] + ec[i] + c[ev[i]][n] == c[1][n])
  147.                 flow.addEdge(2*eu[i]-1, 2*ev[i]-2, oo);
  148.             if (c[1][ev[i]] + ec[i] + c[eu[i]][n] == c[1][n])
  149.                 flow.addEdge(2*ev[i]-1, 2*eu[i]-2, oo);
  150.         }
  151.         int res = flow.getMaxFlow(0, 2*n-1);
  152.         if (res >= oo) cout << "IMPOSSIBLE" << endl;
  153.         else cout << res << endl;
  154.     }
  155.     return 0;
  156. }
  157.  
  158.  
Success #stdin #stdout 0s 3648KB
comments (?)
stdin
copy 
3 3
0 1 1
1 2 1
0 2 3
stdout
copy 
1
https://ideone.com/nypQ08
language:
C++14 (gcc 8.3)
created:
10 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!