PKU 1087 A Plug for UNIX
http://poj.org/problem?id=1087
m個の機器のコンセントの情報と、部屋の中にあるn個のコンセントの情報と、k通りの変換アダプターの情報が与えられるので、最小でいくつの機器がコンセントにつなげられないかを答えろというような問題。
入力の形式が若干面倒くさい二部グラフ最大マッチング。
ワーシャルフロイドでどの形式からどの形式に変換可能かをあらかじめ求めてグラフにしました。
bool wall[300][300]; map<string,int> app; int stoi(string in){ if(app.count(in))return app[in]; int sz=SZ(app); return app[in]=sz; } int recep[100]; int dev[100]; vector<int> G[100]; int match[200]; bool vis[200]; int n,m,k; bool augment(int u){ vis[u]=true; rep(i,SZ(G[u])){ int to=G[u][i]; if(match[to]==-1){ match[u]=to; match[to]=u; return true; } if(!vis[match[to]] && augment(match[to])){ match[to]=u; match[u]=to; return true; } } return false; } main(){ rep(i,300)wall[i][i]=true; cin>>n; rep(i,n){ string in; cin>>in; recep[i]=stoi(in); } cin>>m; rep(i,m){ string name,in; cin>>name>>in; dev[i]=stoi(in); } cin>>k; rep(i,k){ string a,b; cin>>a>>b; wall[stoi(a)][stoi(b)]=true; } rep(l,300){ rep(i,300)rep(j,300)wall[i][j]|=wall[i][l]&wall[l][j]; } memset(match,-1,sizeof(match)); rep(i,m){ rep(j,n)if(wall[dev[i]][recep[j]])G[i].pb(m+j); } int ans=m; rep(i,m){ if(match[i]!=-1)continue; memset(vis,0,sizeof(vis)); if(augment(i))--ans; } cout<<ans<<endl; }