test/aoj/3168.test.cpp

View this file on GitHub
Last update: 2020-10-27 16:27:26+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3168

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3168

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

#define call_from_test
#include "../../io/single.cpp"
#include "../../tools/chminmax.cpp"
#include "../../matching/bipartite.cpp"
#undef call_from_test

const int MAX = 303;
int G[MAX][MAX]={};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m,lim;
  cin>>n>>m>>lim;

  auto cs=read<char>(n);

  const int INF = 1e9;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      G[i][j]=INF;

  for(int i=0;i<n;i++) G[i][i]=0;

  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a][b]=G[b][a]=1;
  }

  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        chmin(G[i][j],G[i][k]+G[k][j]);

  auto check=[&](int i,int j){
    int x=cs[i]-'a';
    int y=cs[j]-'a';
    return (((x+1)%26==y or (y+1)%26==x) and G[i][j]<=lim);
  };

  Bipartite bm(n);
  for(int i=0;i<n;i++)
    for(int j=0;j<i;j++)
      if(check(i,j)) bm.add_edge(i,j);

  cout<<bm.build()<<endl;
  return 0;
}

#line 1 "test/aoj/3168.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3168

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

#define call_from_test
#line 1 "io/single.cpp"

#line 3 "io/single.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "matching/bipartite.cpp"

#line 3 "matching/bipartite.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(N M)
struct Bipartite{
  int time;
  vector< vector<int> > G;
  vector<int> match,used,dead;

  Bipartite(int n):
    time(0),G(n),match(n,-1),used(n,-1),dead(n,0){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  int dfs(int v){
    used[v]=time;
    for(int u:G[v]){
      if(dead[u]) continue;
      int w=match[u];
      if((w<0) or (used[w]<time and dfs(w))){
        match[v]=u;
        match[u]=v;
        return 1;
      }
    }
    return 0;
  }

  int build(){
    int res=0;
    for(int v=0;v<(int)G.size();v++){
      if(dead[v] or ~match[v]) continue;
      time++;
      res+=dfs(v);
    }
    return res;
  }

  int disable(int v){
    assert(!dead[v]);
    int u=match[v];
    if(~u) match[u]=-1;
    match[v]=-1;
    dead[v]=1;
    time++;
    return ~u?dfs(u)-1:0;
  }

  int enable(int v){
    assert(dead[v]);
    dead[v]=0;
    time++;
    return dfs(v);
  }

  int cut_edge(int u,int v){
    assert(find(G[u].begin(),G[u].end(),v)!=G[u].end());
    assert(find(G[v].begin(),G[v].end(),u)!=G[v].end());
    G[u].erase(find(G[u].begin(),G[u].end(),v));
    G[v].erase(find(G[v].begin(),G[v].end(),u));
    if(match[u]==v){
      match[u]=match[v]=-1;
      return 1;
    }
    return 0;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/3168.test.cpp"
#undef call_from_test

const int MAX = 303;
int G[MAX][MAX]={};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m,lim;
  cin>>n>>m>>lim;

  auto cs=read<char>(n);

  const int INF = 1e9;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      G[i][j]=INF;

  for(int i=0;i<n;i++) G[i][i]=0;

  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a][b]=G[b][a]=1;
  }

  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        chmin(G[i][j],G[i][k]+G[k][j]);

  auto check=[&](int i,int j){
    int x=cs[i]-'a';
    int y=cs[j]-'a';
    return (((x+1)%26==y or (y+1)%26==x) and G[i][j]<=lim);
  };

  Bipartite bm(n);
  for(int i=0;i<n;i++)
    for(int j=0;j<i;j++)
      if(check(i,j)) bm.add_edge(i,j);

  cout<<bm.build()<<endl;
  return 0;
}