Facebook
From emanlaicepsa, 1 Month ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 30
  1. //by emanlaicepsa
  2. #include<bits/stdc++.h>
  3. #define ll long long
  4. #define int ll
  5. #define IOS ios::sync_with_stdio(0),cin.tie(0);
  6. #define pb push_back
  7. #define pii pair<int,int>
  8. #define fi first
  9. #define se second
  10. #define all(n) (n).begin(),(n).end()
  11. #define mem(n,k) memset(n,k,sizeof(n))
  12. using namespace std;
  13. template <typename T>
  14. struct hungarian {  // km
  15.   int n;
  16.   vector<int> matchx;
  17.   vector<int> matchy;
  18.   vector<int> pre;
  19.   vector<bool> visx;
  20.   vector<bool> visy;
  21.   vector<T> lx;
  22.   vector<T> ly;
  23.   vector<vector<T> > g;
  24.   vector<T> slack;
  25.   T inf;
  26.   T res;
  27.   queue<int> q;
  28.   int org_n;
  29.   int org_m;
  30.  
  31.   hungarian(int _n, int _m) {
  32.     org_n = _n;
  33.     org_m = _m;
  34.     n = max(_n, _m);
  35.     inf = numeric_limits<T>::max();
  36.     res = 0;
  37.     g = vector<vector<T> >(n, vector<T>(n));
  38.     matchx = vector<int>(n, -1);
  39.     matchy = vector<int>(n, -1);
  40.     pre = vector<int>(n);
  41.     visx = vector<bool>(n);
  42.     visy = vector<bool>(n);
  43.     lx = vector<T>(n, -inf);
  44.     ly = vector<T>(n);
  45.     slack = vector<T>(n);
  46.   }
  47.  
  48.   void addEdge(int u, int v, int w) {
  49.     g[u][v] = max(w, 0LL);  
  50.   }
  51.  
  52.   bool check(int v) {
  53.     visy[v] = true;
  54.     if (matchy[v] != -1) {
  55.       q.push(matchy[v]);
  56.       visx[matchy[v]] = true;
  57.       return false;
  58.     }
  59.     while (v != -1) {
  60.       matchy[v] = pre[v];
  61.       swap(v, matchx[pre[v]]);
  62.     }
  63.     return true;
  64.   }
  65.  
  66.   void bfs(int i) {
  67.     while (!q.empty()) {
  68.       q.pop();
  69.     }
  70.     q.push(i);
  71.     visx[i] = true;
  72.     while (true) {
  73.       while (!q.empty()) {
  74.         int u = q.front();
  75.         q.pop();
  76.         for (int v = 0; v < n; v++) {
  77.           if (!visy[v]) {
  78.             T delta = lx[u] + ly[v] - g[u][v];
  79.             if (slack[v] >= delta) {
  80.               pre[v] = u;
  81.               if (delta) {
  82.                 slack[v] = delta;
  83.               } else if (check(v)) {
  84.                 return;
  85.               }
  86.             }
  87.           }
  88.         }
  89.       }
  90.       // ?有增?路 修改??
  91.       T a = inf;
  92.       for (int j = 0; j < n; j++) {
  93.         if (!visy[j]) {
  94.           a = min(a, slack[j]);
  95.         }
  96.       }
  97.       for (int j = 0; j < n; j++) {
  98.         if (visx[j]) {  // S
  99.           lx[j] -= a;
  100.         }
  101.         if (visy[j]) {  // T
  102.           ly[j] += a;
  103.         } else {  // T'
  104.           slack[j] -= a;
  105.         }
  106.       }
  107.       for (int j = 0; j < n; j++) {
  108.         if (!visy[j] && slack[j] == 0 && check(j)) {
  109.           return;
  110.         }
  111.       }
  112.     }
  113.   }
  114.  
  115.   int solve() {
  116.     // 初始??
  117.     for (int i = 0; i < n; i++) {
  118.       for (int j = 0; j < n; j++) {
  119.         lx[i] = max(lx[i], g[i][j]);
  120.       }
  121.     }
  122.  
  123.     for (int i = 0; i < n; i++) {
  124.       fill(slack.begin(), slack.end(), inf);
  125.       fill(visx.begin(), visx.end(), false);
  126.       fill(visy.begin(), visy.end(), false);
  127.       bfs(i);
  128.     }
  129.  
  130.     // custom
  131.     for (int i = 0; i < n; i++) {
  132.       if (g[i][matchx[i]] > 0) {
  133.         res += g[i][matchx[i]];
  134.       } else {
  135.         matchx[i] = -1;
  136.       }
  137.     }
  138.     return res;
  139.     cout << res << "\n";
  140.     for (int i = 0; i < org_n; i++) {
  141.       cout << matchx[i] + 1 << " ";
  142.     }
  143.     cout << "\n";
  144.   }
  145. };
  146.  
  147.  
  148. int arr[105][105],nx,ny;
  149. int mr[105] , mc[105];
  150.  
  151. signed main(){
  152.         //IOS;
  153.         //mem(w,-1);
  154.         cin>>nx>>ny;
  155.         hungarian<long long> solver(nx, ny);
  156.  
  157.         int tot = 0, cnt = 0;
  158.         for(int i=0;i<nx;i++){
  159.                 for(int j=0;j<ny;j++){
  160.                         cin>>arr[i][j];
  161.                         cnt += (arr[i][j] > 0);
  162.                         tot += (arr[i][j]);
  163.                 }
  164.         }
  165.         for(int i=0;i<nx;i++){
  166.                 mr[i] = 0;
  167.                 for(int j=0;j<ny;j++){
  168.                         mr[i] = max(mr[i],arr[i][j]);
  169.                 }
  170.         }
  171.         for(int j=0;j<ny;j++){
  172.                 mc[j] = 0;
  173.                 for(int i=0;i<nx;i++){
  174.                         mc[j] = max(mc[j],arr[i][j]);
  175.                 }
  176.         }
  177.         int ans = cnt;
  178.         for(int i=0;i<nx;i++) ans += mr[i] , ans -= (mr[i] != 0);
  179.         for(int i=0;i<ny;i++) ans += mc[i] , ans -= (mc[i] != 0);
  180.         for(int i=0;i<nx;i++){
  181.                 if(mr[i] == 0) continue;
  182.                 for(int j=0;j<ny;j++){
  183.                         if(mr[i] == mc[j] && arr[i][j] != 0){
  184.                                 solver.addEdge(i,j,mr[i]-1);
  185.                         }
  186.                 }
  187.         }
  188.         //cout<<solver.solve()<<'\n';
  189.         ans -= solver.solve();
  190.         cout<<tot-ans<<'\n';
  191.         //cout<<"HI\n";
  192.         //ans -= KM();
  193.         //cout<<tot-ans<<'\n';
  194. }
  195.