PKU演習問メモ(6/29)

No.	問題名	問題の種類および解法	難易度
2318	TOYS	幾何（台形と点の包含関係）・二分探索	★★★☆☆
2186	Popular Cows	強連結成分分解・有向グラフの木の判定	★★★★☆
3625	Building Roads	全域木（クラスカル法）	★★★☆☆

2318 TOYS

問題概要

座標軸に平行な長方形をしたおもちゃ箱の頂点の座標が与えられる。
おもちゃ箱の中にはn枚の仕切り板があり、おもちゃ箱の上の辺と下の辺を結んでいて、
上の辺のx座標と下の辺でのx座標が与えられる。

今、m個のおもちゃをそれぞれ座標(x[i],y[i])に投げるとき、仕切り板で区切られたそれぞれの領域に入るおもちゃの数を求めよ。

n≦5000,m≦5000を満たす。

解法

n,mがそこそこ大きいのでおもちゃの入る領域を線形探索などで求めるとTLE（たぶん）。
二分探索をすればO(mlog n)なので十分間に合う。（台形をvectorで作るという非効率なことをしたらTLEになったが……）

台形の領域入るかはベクトルの外積を使うのが楽。（contains関数参照）

ソースコード

typedef complex<double> point;
namespace std {
  bool operator < (const point& a, const point& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const point& a, const point& b) {
  return imag(conj(a)*b);
}
bool contains(const pair<point,point> &lineL,const pair<point,point> &lineR,const point &p)
{
	point dL=lineL.first-lineL.second,dR=lineR.first-lineR.second;
	point dpL=p-lineL.second,dpR=p-lineR.second;
	
	return cross(dL,dpL)<0&&cross(dpR,dR)<0;
}

int n,m;
int main()
{
	while(cin>>n,n)
	{
		int x1,y1,x2,y2;
		scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
		vector<pair<point,point> > line;
		line.pb(mp(point(x1,y1),point(x1,y2)));
		line.pb(mp(point(x2,y1),point(x2,y2)));
		
		rep(i,n)
		{
			int u,l; scanf("%d%d",&u,&l);
			line.pb(mp(point(u,y1),point(l,y2)));
		}
		n+=2;
		sort(all(line));
		
		int cnt[5001]={0};
		rep(i,m)
		{
			int x,y,left=0,right=n-1,mid; scanf("%d%d",&x,&y);
			while(left+1<right)
			{
				mid=(left+right)/2;
				if(contains(line[left],line[mid],point(x,y)))right=mid;
				else left=mid;
			}
			cnt[left]++;
		}
		
		rep(i,n-1)printf("%d: %d\n",i,cnt[i]); puts("");
	}
	return 0;
}

2186 Popular Cows

問題概要

n頭の牛がおり、"牛Aが牛Bをpopularであると思っている"というような関係がm個与えられる。
この関係は推移律を満たす。すなわち牛Aが牛Bをpopularであると思っており、牛Bが牛Cをpopularであると思うとき、牛Aは牛Cをpopularであると思っている。

このとき、全ての他の牛からpopularであると思われている牛の数を求めよ。
n≦10000,m≦50000を満たす。

解法

牛と牛の関係にサイクルがあったとする(A->B->C->Aのような関係)と、A,B,Cのいずれかの牛がpopularであればA,B,Cは全てpopularであり、A,B,Cのいずれかがpopularでなければ全てpopularではない。

したがって、まず牛の関係のグラフの強連結成分分解を行うことを考える。
次に、ある牛が全ての牛からpopularと思われているということは、グラフが木になっていることと同値である。（ただしエッジの向きはAがBをpopularであると思っているときB->Aとしていることに注意）

よって強連結成分のグラフが木になっているかを判定し、なっていなければ0,なっていれば根の頂点の重複数が答えとなる。

有向グラフの木の判定は、DFSを行い、頂点ごとに自分の親を記録していけばできる（親のない頂点が1つだけなら木、そうでないなら木ではない）。

ソースコード

Spaghetti Sourceの強連結成分分解のコードを使用（詳細は右リンクから）

Graph g;
int n,nedge;

vector<vi> scc;
int group[10000],parent[10000],m;

void rec(int cur)
{
	fr(i,scc[cur])fr(j,g[*i])
	{
		if(parent[group[j->dst]]>=0||group[j->dst]==cur)continue;
		parent[group[j->dst]]=cur;
		rec(group[j->dst]);
	}
}

int main()
{
	scanf("%d%d",&n,&nedge);
	g.clear(); g.resize(n);
	
	rep(i,nedge)
	{
		int a,b; scanf("%d%d",&a,&b);
		g[b-1].pb(Edge(b-1,a-1,0));
	}
	scc.clear();
	stronglyConnectedComponents(g,scc);
	rep(i,scc.size())rep(j,scc[i].size())group[scc[i][j]]=i;
	
	m=scc.size();
	rep(i,m)parent[i]=-1;
	rep(i,m)if(parent[i]<0)rec(i);
	
	int child=m,root;
	rep(i,m)if(parent[i]<0)root=i,child--;
	cout<<(child==m-1?scc[root].size():0)<<endl;
	
	return 0;
}

3625 Building Roads

問題概要

平面上にn個の牧場がありそれぞれの座標は(X[i],Y[i])で与えられる。
これらのうちm組のペアは既に道路でつながれている。
全ての牧場を行き来できるようにするために新たに建設する必要がある道路の最小の長さを求めよ。
ただし道路は２つの牧場を直接結ぶようにのみ建設するものとする。

n,m≤1000,
-100000≤X[i],Y[i]≤100000を満たす。

解法

最小全域木（っぽいもの）を求めるのであるが、密グラフであり（各頂点から辺の候補が1000本ある）、更に出発のグラフが木ではなく森であるためプリム法は使いにくい。
クラスカル法が適当であるので実装すればよい。クラスカル法で用いるUnion-Findは経路圧縮のみで制限時間に間に合った。

……初めてクラスカル法書いた。

ソースコード

int n,m,X[1000],Y[1000],nedge;
int p[1000];
pair<ll,pi> edges[1000000];

int root(int a){
  if(p[a]==a)return a;
  return p[a]=root(p[a]);
}
void merge(int a,int b){
  a=root(a); b=root(b);
  if(a!=b)p[a]=b;
}
bool same(int a,int b){
  return root(a)==root(b);
}

int main()
{
  scanf("%d%d",&n,&m);
  rep(i,n)scanf("%d%d",X+i,Y+i),p[i]=i;
  rep(i,m){
    int a,b; scanf("%d%d",&a,&b);
    merge(a-1,b-1);
  }
  rep(i,n)rep(j,i)edges[nedge++]=mp(
    ll(X[i]-X[j])*(X[i]-X[j])+ll(Y[i]-Y[j])*(Y[i]-Y[j]),
    mp(i,j));
  sort(edges,edges+nedge);

  int nisland=0; double ans=0;
  bool visited[1000]={0};
  rep(i,n)if(!visited[root(i)])visited[root(i)]=1,nisland++;

  for(int i=0;i<nedge&&nisland>1;i++)
  if(!same(edges[i].second.first,edges[i].second.second))
  {
    ans+=sqrt(double(edges[i].first));
    merge(edges[i].second.first,edges[i].second.second);
    nisland--;
  }
  printf("%.2f\n",ans);

  return 0;
}