fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. //#pragma GCC optimize("unroll-loops")
  10. //#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
  11. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  12. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  13. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  14. #define fi first
  15. #define se second
  16. #define M 1000000007
  17. #define MAXN 1000001
  18. #define INF (1ll<<31)
  19. #define BLOCK_SIZE 425
  20. #define MAX_NODE 1001001
  21. #define LOG 19
  22. #define ALPHA_SIZE 26
  23. #define BASE 311
  24. #define NAME "file"
  25. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  26. using namespace std;
  27. using namespace chrono ;
  28. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  29. const ll NMOD = 1;
  30. const int dx[] = {-1, 0, 1,0};
  31. const int dy[] = {0, 1, 0, -1};
  32. //**Variable**//
  33. ll n, low, high, ans;
  34. ll arr[201][201];
  35. ll d[MAXN] ;
  36. vector<ll> adj[MAXN] ;
  37. ll curPos[MAXN] ;
  38. //**Struct**//
  39. struct Edge {
  40.     ll u, v, flow, capa ;
  41.     Edge() {
  42.         u = v = flow = capa = 0 ;
  43.     }
  44.     Edge(ll _u, ll _v, ll _flow, ll _capa) {
  45.         u = _u, v = _v, flow = _flow, capa = _capa ;
  46.     }
  47.     ll flowExit() {
  48.         return capa - flow ;
  49.     }
  50. } edge[MAXN];
  51. bool  bfs(ll start ) {
  52.     FOR(i, 0, 2*n + 1 ) d[i] = INF ;
  53.     d[start] = 0 ;
  54.     queue<ll> q;
  55.     q.push(start  ) ;
  56.     while(!q.empty()) {
  57.         ll u = q.front() ;
  58.         q.pop() ;
  59.         for(ll id  : adj[u]) {
  60.             ll v = edge[id].v ;
  61.             if(d[v] != INF || !edge[id].flowExit()) continue ;
  62.             d[v] = d[u] + 1 ;
  63.             q.push(v) ;
  64.         }
  65.     }
  66.     return d[2*n+1] != INF ;
  67. }
  68. ll dfs(ll u, ll curFlow) {
  69.     if(u == 2*n + 1  ) return curFlow ;
  70.     if(curFlow == 0) return curFlow ;
  71.     for(; curPos[u] < adj[u].size() ; curPos[u] ++ ) {
  72.         ll id = adj[u][curPos[u]] ;
  73.         ll v = edge[id].v ;
  74.         if(d[v] != d[u] +1 || !edge[id].flowExit()) continue ;
  75.         ll delta = dfs(v, min(curFlow, edge[id].flowExit())) ;
  76.         if(delta == 0  ) continue ;
  77.         edge[id].flow += delta ;
  78.         edge[id^1].flow -= delta ;
  79.         return delta ;
  80.     }
  81.     return 0 ;
  82. }
  83. //**Function**//
  84. template<class X, class Y >
  85. bool minimize(X & x, const Y &y ) {
  86.     return x > y ? x = y, 1:0 ;
  87. }
  88. template<class X, class Y >
  89. bool maximize(X &x, const Y &y ) {
  90.     return x < y ? x = y, 1:0 ;
  91. }
  92.  
  93. void init() {
  94.     cin>>n;
  95.     low = INF ;
  96.     FOR(i,1, n) {
  97.         FOR(j, 1, n ) {
  98.             cin >> arr[i][j] ;
  99.             maximize(high, arr[i][j]) ;
  100.             minimize(low, arr[i][j] ) ;
  101.         }
  102.     }
  103. }
  104. bool check(ll m ) {
  105.     ll cnt = 0, maxFlow = 0 ;
  106.     FOR(i, 1, n ) {
  107.         edge[cnt<<1] = Edge(0, i, 0, 1) ;
  108.         edge[cnt<<1|1] = Edge(i, 0, 0, 0 ) ;
  109.         adj[0].push_back(cnt<<1 ) ;
  110.         adj[i].push_back(cnt<<1|1) ;
  111.         cnt ++ ;
  112.     }
  113.     FOR(i, n+1, 2 * n ) {
  114.         edge[cnt<<1] = Edge(i, 2 * n+ 1, 0, 1) ;
  115.         edge[cnt<<1|1] = Edge(2*n+1, i, 0, 0 ) ;
  116.         adj[i].push_back(cnt<<1) ;
  117.         adj[2*n+1].push_back(cnt<<1|1) ;
  118.         cnt ++ ;
  119.     }
  120.     FOR(i, 1,  n ) FOR(j, 1,n ) {
  121.         if(arr[i][j] <= m ) {
  122.             edge[cnt << 1 ] = Edge(i, j+n, 0, 1 ) ;
  123.             edge[cnt<<1|1] = Edge(j+n, i, 0, 0) ;
  124.             adj[i].push_back(cnt<<1) ;
  125.             adj[j+n].push_back(cnt<<1|1) ;
  126.             cnt ++ ;
  127.         }
  128.     }
  129.     while(bfs(0)) {
  130.         FOR(i, 0, 2 * n + 1 ) curPos[i] = 0 ;
  131.         while(int  x = dfs(0, INF)) maxFlow += x;
  132.     }
  133.     FOR(i, 0, 2*n + 1 ) adj[i].resize(0) ;
  134.     return maxFlow == n ;
  135. }
  136.  
  137. void solve() {
  138.     while(low<= high ) {
  139.         ll m = low + high >> 1;
  140.         if(check(m) ) {
  141.             ans = m ;
  142.             high= m -1 ;
  143.         } else low = m + 1 ;
  144.     }
  145.     cout << ans ;
  146. }
  147.  
  148. __ROOT__ {
  149.     // freopen(NAME".inp" , "r" , stdin);
  150.     // freopen(NAME".out" , "w", stdout) ;
  151.     fast;
  152.     int t = 1; // cin >> t ;
  153.     while(t--) {
  154.         init();
  155.         solve();
  156.     }
  157.     return (0&0);
  158. }
  159.  
  160.  
  161.  
  162.  
Success #stdin #stdout 0.02s 61952KB
comments (?)
stdin
copy 
4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10
stdout
copy 
5
https://ideone.com/4VHK7r
language:
C++14 (clang 8.0)
created:
168 days 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!