Advertisement
yungyao

Untitled

Aug 11th, 2022
854
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.99 KB | None | 0 0
  1. /*
  2.  
  3.  
  4. weak        weak  we      ak   we  akwea        weak  we
  5.   weak    weak    we      ak   weak    weak    we  ak we
  6.     weakweak      we      ak   wea       ak   we    akwe
  7.       wea         we      ak   we        ak   we    akwe
  8.       wea         we      ak   we        ak   we    akwe
  9.       wea          eak  weak   we        ak    we  ak we
  10.       wea            wea  ak   we        ak     weak  we
  11.                                                       we
  12. we      ak     wea  ak       weak                     we
  13.  we    ak    wea  weak     wea  eak                   we
  14.   we  ak    we      ak   wea      wea         we      we
  15.    weak     we      ak   we        we         we      we
  16.     we      we      ak   we        we         we      we
  17.    we        wea  weak    wea    wea          weak  weak
  18. weak           wea  akw      weak                weak
  19.  
  20.  
  21. */
  22. //#define _GLIBCXX_DEBUG //is only used when couldn't find bug
  23. using namespace std;
  24. #pragma GCC optimize ("Ofast")
  25. /*
  26. Never gonna give you up
  27. Never gonna let you down
  28. Never gonna run around and desert you
  29. Never gonna make you cry
  30. Never gonna say goodbye
  31. Never gonna tell a lie and hurt you
  32. */
  33. //headers
  34. #include <vector>
  35. #include <queue>
  36. #include <algorithm>
  37. #include <cmath>
  38. #include <utility>
  39. #include <bitset>
  40. #include <set>
  41. #include <string>
  42. #include <stack>
  43. #include <iomanip>
  44. #include <map>
  45. #include <memory.h>
  46. #include <deque>
  47. #include <time.h>
  48. #include <assert.h>
  49. #include <unordered_map>
  50. #include <unordered_set>
  51. #include <sstream>
  52. #include <random>
  53.  
  54. //defines
  55. typedef long long LL;
  56. typedef pair<int,int> pii;
  57. typedef pair<LL,LL> pll;
  58. typedef vector<int> vi;
  59. typedef vector<LL> vl;
  60. typedef vector<vector<int>> vvi;
  61. typedef vector<vector<LL>> vvl;
  62. #define pb push_back
  63. #define F first
  64. #define S second
  65. #define mid (LB+RB)/2
  66. #define mkp make_pair
  67.  
  68. //iterators
  69. #define iter(x) x.begin(),x.end()
  70. #define aiter(a,n) a,a+n
  71.  
  72. //loops
  73. #define REP(n) for (int ___=n > 0 ? n : 0;___--;)
  74. #define REP0(i,n) for (int i=0,___=n;i<___;++i)
  75. #define REP1(i,n) for (int i=1,___=n;i<=___;++i)
  76. #define MEM(e,val) memset (e,val,sizeof(e))
  77.  
  78. /*
  79. When he said Super Idol的笑容 都没你的甜 八月正午的阳光 都没你耀眼 热爱105℃的你 滴滴清纯的蒸馏水 你不知道你有多可爱 跌倒后会傻笑着再站起来 你从来都不轻言失败 对梦想的执着一直不曾更改 很安心 当你对我说 不怕有我在 放着让我来 勇敢追自己的梦想 那坚定的模样 Super Idol的笑容 都没你的甜 八月正午的阳光 都没你耀眼 热爱105℃的你 滴滴清纯的蒸馏水 在这独一无二 属于我的时代 不怕失败来一场 痛快的热爱 热爱105℃的你 滴滴清纯的蒸馏水 在这独一无二 属于我的时代 莫忘了初心常在 痛快去热爱 爱105℃的你 滴滴清纯的蒸馏水 喝一口又活力全开 再次回到最佳状态 喝一口哟 你不知道你有多可爱 跌倒后会傻笑着再站起来 你从来都不轻言失败 对梦想的执着一直不曾更改 很安心 当你对我说 不怕有我在 放着让我来 勇敢追自己的梦想 那坚定的模样 Super Idol的笑容 都没你的甜 八月正午的阳光 都没你耀眼 热爱105℃的你 滴滴清纯的蒸馏水 在这独一无二 属于我的时代 不怕失败来一场 痛快的热爱 热爱105℃的你 滴滴清纯的蒸馏水 在这独一无二 属于我的时代 莫忘了初心常在 痛快去热爱 热爱105℃的你 滴滴清纯的蒸馏水 喝一口又活力全开 再次回到最佳状态 喝一口又活力全开
  80. I really felt that.
  81.  
  82.  
  83. every one is so dian except me
  84. still too weak 咩噗
  85. */
  86.  
  87. //IO
  88. #include <cstdio>
  89. #include <iostream>
  90. #include <fstream>
  91. #define want_to_be_more_dian ios_base::sync_with_stdio(false),cin.tie(0);
  92.  
  93. //pbds
  94. /*
  95. #include <ext/pb_ds/tree_policy.hpp>
  96. #include <ext/pb_ds/assoc_container.hpp>
  97. #include <ext/pb_ds/priority_queue.hpp>
  98. using namespace __gnu_pbds;
  99. //tree <pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>;
  100. */
  101.  
  102. //constants
  103. #include <climits>
  104. const int maxn = 230,mod = 0;
  105. const long long INF = LLONG_MAX;
  106. const double eps = 0;
  107.  
  108. //workspace
  109.  
  110. #define int LL
  111. struct DIN{
  112.     struct E{
  113.         LL v, c, r;
  114.         E(int v, int c, int r):
  115.             v(v), c(c), r(r){}
  116.     };
  117.     vector<E> adj[maxn];
  118.     void add(int u, int v, int c){
  119.         adj[u].pb(E(v, c, (int) adj[v].size()));
  120.         adj[v].pb(E(u, 0, (int) adj[u].size() - 1));
  121.     }
  122.     int n, s, t;
  123.     void init(int nn, int ss, int tt){
  124.         n = nn, s = ss, t = tt;
  125.         for(int i = 0; i <= n; ++i)
  126.             adj[i].clear();
  127.     }
  128.     int le[maxn], it[maxn];
  129.     int bfs(){
  130.         fill(le, le + maxn, -1); le[s] = 0;
  131.         queue<int> q; q.push(s);
  132.         while(!q.empty()){
  133.             int u = q.front(); q.pop();
  134.             for(auto [v, c, r]: adj[u]){
  135.                 if(c > 0 && le[v] == -1)
  136.                     le[v] = le[u] + 1, q.push(v);
  137.             }
  138.         }
  139.         return ~le[t];
  140.     }
  141.     int dfs(int u, int f){
  142.         if(u == t) return f;
  143.         for(int &i = it[u]; i < (int) adj[u].size(); ++i){
  144.             auto &[v, c, r] = adj[u][i];
  145.             if(c > 0 && le[v] == le[u] + 1){
  146.                 int d = dfs(v, min(c, f));
  147.                 if(d > 0){
  148.                     c -= d;
  149.                     adj[v][r].c += d;
  150.                     return d;
  151.                 }
  152.             }
  153.         }
  154.         return 0;
  155.     }
  156.     LL flow(){
  157.         LL ans = 0, d;
  158.         while(bfs()){
  159.             fill(it, it + maxn, 0);
  160.             while((d = dfs(s, INF)) > 0) ans += d;
  161.         }
  162.         return ans;
  163.     }
  164. } din;
  165.  
  166. int adj[501][501];
  167.  
  168. inline void solve(){
  169.     int n;
  170.  
  171.     cin >> n;
  172.     int m = (n+1)/2;
  173.     REP1(i, n) REP1(j, n) cin >> adj[i][j];
  174.     din.init(m * 2+1, 0, m*2+1);
  175.     REP1(i, m){
  176.         din.add(0, i, INF);
  177.         din.add(m+i, m*2+1, INF);
  178.     }
  179.     for (int i=1;i<=n;i+=2){
  180.         din.add(i/2+1, m+1, adj[i][1]);
  181.         for (int j=3;j<n;j+=2){
  182.             din.add(i/2+1, m+j/2+1, adj[j-1][i] + adj[i][j+1]);
  183.         }
  184.         if (n & 1) din.add(i/2+1, m*2, adj[i][n-1]);
  185.     }
  186.     cout << din.flow();
  187. }
  188.  
  189. signed main(){
  190.     want_to_be_more_dian
  191.     //int t,i=1; for (int ;cin;)//use in multi-testcases and end in EOF problems
  192.     //int t,i=1; for (cin >> t;i<=t;++i)//use in multi-testcases problems
  193.     //cout << "Case #" << i << ": ",//use in Google, FB competitions
  194.     solve();//always used
  195.     return 0;
  196. }
  197.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement