4654 - Tracking Robots

ACM-ICPC live archive

4654 - Tracking Robots Asia - Tehran - 2009/2010
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4654

問題概要

土地がいくつかの領域に区切られている。
ロボットが1番地に何台かいる。
ロボットがどこかの領域に進入する度に、どこの領域に進入したかという、
履歴が残されている（どのロボットかどうかは不明）。
このとき、考えられるロボットの最大台数と最小台数を答えよ。
ただし、ロボットは最低一回はどこかの領域に進入しているとする。

解法

最小の場合　二部マッチング

まず、ノードは履歴の記録とする。
履歴と履歴をマッチングする。
張るエッジは、ある記録から

  • その記録よりも後の記録であること。
  • その記録の領域から直接たどり着ける領域の記録であること。

を両方を満たすノードへエッジを張る。
そうすると、「ある履歴を終えたロボットに仕事を割り当てる」ということと同値になる。
もし、まったく仕事が割り当てられないなら、履歴の数分ロボットが必要であることから、
履歴の数　- 最大マッチング
が、最小のロボットの台数である。
ある記録に仕事が割り当てられると、その記録のためにロボットを用意する必要がなくなるので、引けばよい。

最大の場合

よく考えると初期位置から1ステップでいける領域が履歴に何個含まれているかでよい。
ロボットの出動を最大にするためには、

  • 直接たどり着けない領域へ移動するためには、新たに出動させたロボットでは移動不可能である。
  • 直接たどり着ける領域に新たにロボットを出動させ向かわせても、その後の移動の実現に支障はない。

これらのことから、初期位置から直接たどり着ける領域がいくつ履歴に含まれるかで最大の台数がわかる。

ソース

#include<iostream>
#include<string>
#include<vector>
#include<cstring>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;
 const int MAX_V = 400;
 vector<int> G[MAX_V];
 int match[MAX_V];
 bool used[MAX_V];

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

 bool dfs(int v){
   used[v] = true;
   rep(i, (int)G[v].size()){
     int u = G[v][i], w = match[u];
     if(w < 0 || (!used[w] && dfs(w))){
       match[v] = u;
       match[u] = v;
       return true;
     }
   }
   return false;
 }

 int bipartite_matching(int V){
   int res = 0;
   memset(match, -1,  sizeof(match));
   rep(i, V){
     if(match[i] < 0){
       memset(used, 0, sizeof(used));
       if(dfs(i)){
         res++;
       }
     }
   }
   return res;
 }

void clear_edge(){
  rep(i, MAX_V){
    G[i].clear();
  }
}

int main(){
  int n, m;
  while(cin >> n >> m){
    bool edge[100][100];
    int stream[200], mini, maxi;
    if(n == 0 && m == 0)break;
    rep(i, 100){
      rep(j, 100){
        edge[i][j] = false;
      }
    }
    rep(i, n){
      int e;
      cin >> e;
      rep(j, e){
        int to;
        cin >> to;
        edge[i][to-1] = true;
      }
    }
    rep(i, m){
      cin >> stream[i];
      stream[i]--;
    }
    clear_edge();
    rep(i, m){
      REP(j, i+1, m){
        if(!edge[stream[i]][stream[j]])continue;
        add_edge(i, m+j);
      }
    }
    mini = m - bipartite_matching(m*2);
    maxi = 0;
    rep(i, m){
      if(edge[0][stream[i]])maxi++;
    }
    cout << mini << ' ' << maxi << endl;
  }
  return 0;
}