paulomiranda98

Olimpíadas - Maratona 2007

Sep 21st, 2020
788
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define PB push_back
  6. #define all(x) x.begin(),x.end()
  7. #define endl '\n'
  8. #define W(x) cerr << "\033[31m"<<  #x << " = " << x << "\033[0m" << endl;
  9.  
  10. using namespace std;
  11. std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
  12.  
  13. using ll = long long;
  14. using pii = pair<int, int>;
  15.  
  16. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  17. const int MOD = 1000000007;
  18. template <class T = int>
  19. class MCMF{
  20. private:
  21.   struct Edge{
  22.     int to;
  23.     T cap, cost;
  24.     Edge(int a, T b, T c) : to(a), cap(b), cost(c) {}
  25.   };
  26.   int n;
  27.   vector<vector<int>> edges;
  28.   vector<Edge> list;
  29.   vector<int> from;
  30.   vector<T> dist, pot;
  31.   vector<bool> visit;
  32.   pair<T, T> augment(int src, int sink){
  33.     pair<T, T> flow = {list[from[sink]].cap, 0};
  34.     for (int v = sink; v != src; v = list[from[v] ^ 1].to){
  35.       flow.first = std::min(flow.first, list[from[v]].cap);
  36.       flow.second += list[from[v]].cost;
  37.     }
  38.     for (int v = sink; v != src; v = list[from[v] ^ 1].to){
  39.       list[from[v]].cap -= flow.first;
  40.       list[from[v] ^ 1].cap += flow.first;
  41.     }
  42.     return flow;
  43.   }
  44.   queue<int> q;
  45.   bool SPFA(int src, int sink){
  46.     T INF = numeric_limits<T>::max();
  47.     dist.assign(n, INF);
  48.     from.assign(n, -1);
  49.     q.push(src);
  50.     dist[src] = 0;
  51.     while (!q.empty()){
  52.       int on = q.front();
  53.       q.pop();
  54.       visit[on] = false;
  55.       for (auto e : edges[on]){
  56.         auto ed = list[e];
  57.         if (ed.cap == 0)
  58.           continue;
  59.         T toDist = dist[on] + ed.cost + pot[on] - pot[ed.to];
  60.         if (toDist < dist[ed.to]){
  61.           dist[ed.to] = toDist;
  62.           from[ed.to] = e;
  63.           if (!visit[ed.to]){
  64.             visit[ed.to] = true;
  65.             q.push(ed.to);
  66.           }
  67.         }
  68.       }
  69.     }
  70.     return dist[sink] < INF;
  71.   }
  72.   void fixPot(){
  73.     T INF = numeric_limits<T>::max();
  74.     for (int i = 0; i < n; i++){
  75.       if (dist[i] < INF)
  76.         pot[i] += dist[i];
  77.     }
  78.   }
  79. public:
  80.   MCMF(int size){
  81.     n = size;
  82.     edges.resize(n);
  83.     pot.assign(n, 0);
  84.     dist.resize(n);
  85.     visit.assign(n, false);
  86.   }
  87.   pair<T, T> solve(int src, int sink, int mx){
  88.     pair<T, T> ans(0, 0);
  89.     // Can use dijkstra to speed up depending on the graph
  90.     if (!SPFA(src, sink))
  91.       return ans;
  92.     fixPot();
  93.     // Can use dijkstra to speed up depending on the graph
  94.     while (SPFA(src, sink)){
  95.       auto flow = augment(src, sink);
  96.       if(flow.S > mx)
  97.         break;
  98.       ans.first += flow.first*(mx-flow.second+1);
  99.       ans.second += flow.first * flow.second;
  100.       fixPot();
  101.     }
  102.     return ans;
  103.   }
  104.   void addEdge(int u, int to, T cap, T cost){
  105.     edges[u].push_back(list.size());
  106.     list.push_back(Edge(to, cap, cost));
  107.     edges[to].push_back(list.size());
  108.     list.push_back(Edge(u, 0, -cost));
  109.   }
  110. };
  111. struct Edge{
  112.   int a, b, s;  
  113. };
  114. int main() {
  115.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  116.   while(true){
  117.     int n, m, a;
  118.     cin >> n >> m >> a;
  119.     if(n==0 and m==0 and a==0)
  120.       break;
  121.     vector<Edge> edges(m);
  122.     for(int i=0; i<m; i++){
  123.       cin >> edges[i].a >> edges[i].b >> edges[i].s;
  124.     }
  125.     int lo=1, hi=1000, ans=1000;
  126.     while(lo<=hi){
  127.       int mid = (lo+hi)/2;
  128.       MCMF mcmf(n);
  129.       for(int i=0; i<m; i++)
  130.         mcmf.addEdge(edges[i].a-1, edges[i].b-1, edges[i].s, 1);
  131.       if(mcmf.solve(0, n-1, mid).F >= a){
  132.         ans = mid;
  133.         hi = mid-1;
  134.       }else{
  135.         lo = mid+1;
  136.       }
  137.     }
  138.     cout << ans << endl;
  139.   }
  140.   cout << endl;
  141.   return 0;
  142. }
RAW Paste Data