test/aoj/3183.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 18:08:33+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3183

Depends on

• graph/dijkstra.cpp
• graph/stronglyconnectedcomponent.cpp
• 最大流 (計算量が流量依存) (maxflow/fordfulkerson.cpp)
• tools/drop.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3183"

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

#define call_from_test
#include "../../tools/drop.cpp"
#include "../../graph/stronglyconnectedcomponent.cpp"
#include "../../graph/dijkstra.cpp"
#include "../../maxflow/fordfulkerson.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

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

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

  int n,m;
  cin>>n>>m;
  SCC G(n);

  int S=n,T=n+1;
  Dijkstra<int> D(n+2);
  FordFulkerson<int, true> F(n+2);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    G.add_edge(u,v);
    D.add_edge(u,v,1);
    F.add_edge(u,v,1);
  }
  int k=G.build();

  vector<int> indeg(n,0);
  vector<int> outdeg(n,0);

  for(int i=0;i<k;i++)
    for(int j:G.H[i])
      outdeg[i]++,indeg[j]++;

  for(int i=0;i<k;i++){
    if(i!=0 and indeg[i]==0) drop(-1);
    if(i!=k-1 and outdeg[i]==0) drop(-1);
  }

  for(int i=0;i<n;i++){
    if(G.blg[i]==0){
      D.add_edge(S,i,0);
      F.add_edge(S,i,2);
    }
    if(G.blg[i]==k-1){
      D.add_edge(i,T,0);
      F.add_edge(i,T,2);
    }
  }

  int res=F.flow(S,T,2);
  if(res!=2) drop(-1);

  D.build(S);
  if(~D.bs[T]) drop(D[T]);
  drop(-1);
  return 0;
}

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

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

#define call_from_test
#line 1 "tools/drop.cpp"

#line 3 "tools/drop.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "graph/stronglyconnectedcomponent.cpp"

#line 3 "graph/stronglyconnectedcomponent.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct SCC{
  vector< vector<int> > G,R,H,C;
  vector<int> vs,used,blg;
  SCC(int n):G(n),R(n),used(n),blg(n){}

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

  void dfs(int v){
    used[v]=1;
    for(int u:G[v])
      if(!used[u]) dfs(u);
    vs.emplace_back(v);
  }

  void rdfs(int v,int k){
    used[v]=1;
    blg[v]=k;
    C[k].emplace_back(v);
    for(int u:R[v])
      if(!used[u]) rdfs(u,k);
  }

  int build(bool uniq=true){
    int n=G.size();
    for(int v=0;v<n;v++)
      if(!used[v]) dfs(v);

    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=n-1;i>=0;i--){
      if(!used[vs[i]]){
        H.emplace_back();
        C.emplace_back();
        rdfs(vs[i],k++);
      }
    }

    for(int v=0;v<n;v++)
      for(int u:G[v])
        if(blg[v]!=blg[u])
          H[blg[v]].emplace_back(blg[u]);

    if(uniq){
      for(int i=0;i<k;i++){
        sort(H[i].begin(),H[i].end());
        H[i].erase(unique(H[i].begin(),H[i].end()),H[i].end());
      }
    }
    return k;
  }

  int operator[](int k) const{return blg[k];}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "graph/dijkstra.cpp"

#line 3 "graph/dijkstra.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct Dijkstra{
  struct Edge{
    int to;
    T cost;
    Edge(int to,T cost):to(to),cost(cost){}
    bool operator<(const Edge &o)const{return cost>o.cost;}
  };

  vector< vector<Edge> > G;
  vector<T> ds;
  vector<int> bs;
  Dijkstra(int n):G(n){}

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

  void build(int s){
    int n=G.size();
    ds.assign(n,numeric_limits<T>::max());
    bs.assign(n,-1);

    priority_queue<Edge> pq;
    ds[s]=0;
    pq.emplace(s,ds[s]);

    while(!pq.empty()){
      auto p=pq.top();pq.pop();
      int v=p.to;
      if(ds[v]<p.cost) continue;
      for(auto e:G[v]){
        if(ds[e.to]>ds[v]+e.cost){
          ds[e.to]=ds[v]+e.cost;
          bs[e.to]=v;
          pq.emplace(e.to,ds[e.to]);
        }
      }
    }
  }

  T operator[](int k){return ds[k];}

  vector<int> restore(int to){
    vector<int> res;
    if(bs[to]<0) return res;
    while(~to) res.emplace_back(to),to=bs[to];
    reverse(res.begin(),res.end());
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "maxflow/fordfulkerson.cpp"

#line 3 "maxflow/fordfulkerson.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(F E)
template<typename Flow, bool directed>
struct FordFulkerson{
  struct Edge{
    int dst;
    Flow cap;
    int rev;
    Edge(int dst,Flow cap,int rev):dst(dst),cap(cap),rev(rev){}
  };

  vector< vector<Edge> > G;
  vector<int> used;

  FordFulkerson(int n):G(n),used(n){}

  int add_edge(int src,int dst,Flow cap){
    int e=G[src].size();
    int r=(src==dst?e+1:G[dst].size());
    G[src].emplace_back(dst,cap,r);
    G[dst].emplace_back(src,directed?0:cap,e);
    return e;
  }

  Flow dfs(int v,int t,Flow f){
    if(v==t) return f;
    used[v]=true;
    for(Edge &e:G[v]){
      if(used[e.dst] or e.cap==0) continue;
      Flow d=dfs(e.dst,t,min(f,e.cap));
      if(d==0) continue;
      e.cap-=d;
      G[e.dst][e.rev].cap+=d;
      return d;
    }
    return 0;
  }

  Flow flow(int s,int t,Flow lim){
    Flow res=0;
    while(1){
      fill(used.begin(),used.end(),0);
      Flow f=dfs(s,t,lim);
      if(f==0) break;
      res+=f;
      lim-=f;
    }
    return res;
  }

  Flow flow(int s,int t){
    return flow(s,t,numeric_limits<Flow>::max()/2);
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 11 "test/aoj/3183.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

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

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

  int n,m;
  cin>>n>>m;
  SCC G(n);

  int S=n,T=n+1;
  Dijkstra<int> D(n+2);
  FordFulkerson<int, true> F(n+2);
  for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    G.add_edge(u,v);
    D.add_edge(u,v,1);
    F.add_edge(u,v,1);
  }
  int k=G.build();

  vector<int> indeg(n,0);
  vector<int> outdeg(n,0);

  for(int i=0;i<k;i++)
    for(int j:G.H[i])
      outdeg[i]++,indeg[j]++;

  for(int i=0;i<k;i++){
    if(i!=0 and indeg[i]==0) drop(-1);
    if(i!=k-1 and outdeg[i]==0) drop(-1);
  }

  for(int i=0;i<n;i++){
    if(G.blg[i]==0){
      D.add_edge(S,i,0);
      F.add_edge(S,i,2);
    }
    if(G.blg[i]==k-1){
      D.add_edge(i,T,0);
      F.add_edge(i,T,2);
    }
  }

  int res=F.flow(S,T,2);
  if(res!=2) drop(-1);

  D.build(S);
  if(~D.bs[T]) drop(D[T]);
  drop(-1);
  return 0;
}

Back to top page