1161 Walls

問題概要

壁によってM個の領域に仕切られた国がある。
国内にはN個の町があり、町の中心と町の中心をつなぐように壁は立てられている。

町のうちL個にクラブの会員が一人ずついて、クラブの集会を開く。
会員は領域から領域へ移動するとき壁を越えなければならない。各会員が壁を越える回数の合計を最小にするような領域を求め、そのときの壁を越える回数の合計を出力せよ。

M≦200,N≦250,L≦30を満たす。

解法

どこが町なのか問題文から読み取りにくいが、グラフの頂点が町。
頂点からは最初どの領域へもコスト０で移動できることに注意。

考えるのは双対なグラフ。
最初のグラフをF,Fの双対なグラフをGとすれば、Gは、グラフFの各領域を頂点として、Fのグラフで隣り合う領域同士を辺で結んだグラフ。

双対なグラフGは、以下のように作ればよい。

• Fの二つの領域A,Bが同じ辺を共有するならそれは隣接しているので、Gの頂点A,Bを辺で結ぶ。

双対グラフ上でワーシャルフロイドをすれば各領域間の最短距離（壁を越える数）が求められる。
全ての領域について、会員の移動距離の合計を求めて、それが最小となるような場所を探せばよい。

壁は微妙に数が多いので二分探索（下のコードではSTLのsetを使用）する必要があるかも。

ソースコード

set<pi> S[250]; set<int> T[250];
int m,n,l,p[30],e[200][200];

int main()
{
	scanf("%d%d%d",&m,&n,&l);
	rep(i,l)scanf("%d",p+i);
	rep(i,m)
	{
		int a,b[250],c,d; scanf("%d",&a);
		rep(j,a)scanf("%d",b+j),T[b[j]].insert(i);
		rep(j,a)
		{
			c=b[j]; d=b[(j+1)%a];
			if(c>d)swap(c,d); S[i].insert(mp(c,d));
		}
	}
	
	rep(j,m)rep(i,j)
	{
		e[i][j]=e[j][i]=inf;
		fr(it,S[i])if(S[j].count(*it))
		{
			e[i][j]=e[j][i]=1;
			break;
		}
	}
	rep(k,m)rep(i,m)rep(j,m)e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
	
	int ans=inf;
	rep(i,m)
	{
		int sum=0;
		rep(j,l)
		{
			int mn=inf;
			fr(k,T[p[j]])mn=min(mn,e[i][*k]);
			sum+=mn;
		}
		ans=min(ans,sum);
	}
	printf("%d\n",ans);
	
	return 0;
}