matching/tutte.cpp

• View this file on GitHub
• Last update: 2021-03-25 09:46:10+09:00

Depends on

• mod/mint.cpp

Verified with

• test/aoj/2983.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../mod/mint.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
int maximal_matching(vector< vector<int> > G){
  int n=G.size();

  random_device rd;
  mt19937 mt(rd());
  using M = Mint<int>;
  uniform_int_distribution<int> ud(1,M::mod-1);

  vector< vector<M> > H(n,vector<M>(n,0));
  for(int v=0;v<n;v++){
    for(int u:G[v]){
      if(u>=v) continue;
      M val(ud(mt));
      H[u][v]= val;
      H[v][u]=-val;
    }
  }

  int res=0;
  for(int i=0,j=0;i<n;i++){
    while(j<n and H[i][j]==M(0)){
      int p=i;
      for(int k=i+1;k<n;k++)
        if(H[k][j]!=M(0)) p=k;
      if(i!=p) swap(H[i],H[p]);
      else j++;
    }
    if(j==n) break;
    M tmp=H[i][j].inv();
    for(int s=j;s<n;s++) H[i][s]*=tmp;
    for(int k=i+1;k<n;k++)
      for(int s=n-1;s>=j;s--)
        H[k][s]-=H[k][j]*H[i][s];

    j++;res++;
  }
  return (res+1)/2;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: matching/tutte.cpp: line 6: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page