PKU演習問メモ(8/25)

もうだめぽorz

No.	問題名	問題の種類および解法	難易度
2349	Arctic Network	クラスカル法	★★★☆☆
2394	Checking an Alibi	ダイクストラ法	★★☆☆☆
2376	Cleaning Shifts	貪欲法	★★☆☆☆

2349 Arctic Network

問題概要

n個の部隊の位置（平面上での座標）と衛星通信機の数sが与えられる。
衛星通信機を持っている部隊同士は位置にかかわらず通信ができるが、それを持っていない部隊はトランシーバーで連絡しなければならないため、D以下の距離にいなければ通信できない。

n,sおよび各部隊の座標が与えられたとき、全ての部隊間が（直接または間接に）通信可能となるようなDの値の最小値を求めよ。

解法

outpostは前哨部隊のことらしい。

クラスカル法を途中で打ち切る。
すなわち、（島の数＝必要な衛星通信機の数）がsで足りるようになるまで、どんどん近い部隊にトランシーバで通信でしてもらう（Dを大きくしていく）。

ソースコード

int s,n,ne;
pair<double,pi> e[500*500];

int p[500];
int root(int x)
{
	if(x==p[x])return x;
	return p[x]=root(p[x]);
}

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d",&s,&n);
		
		int x[500],y[500];
		rep(i,n)scanf("%d%d",x+i,y+i),p[i]=i;
		ne=0;
		rep(i,n)rep(j,i)e[ne++]=mp(hypot(x[i]-x[j],y[i]-y[j]),mp(i,j));
		sort(e,e+ne);
		
		int m=n; double ans=0;
		for(int ei=0;m>s;ei++)
		{
			int a=e[ei].second.first,b=e[ei].second.second;
			a=root(a); b=root(b);
			if(a==b)continue;
			m--; ans=e[ei].first;
			p[a]=b;
		}
		printf("%.2f\n",ans);
	}
	return 0;
}

2394 Checking an Alibi

問題概要

1番の牧場で犯罪がおこった。M秒前の衛星写真に全ての容疑者の場所が写っており
それぞれの牧場間の移動時間の情報があたえられる。

このとき、容疑者となる牛を全て出力せよ。
F（牧場の数）≦500,
P（牧場間の道の数）≦1000.
C（牛の数）≦100を満たす。

解法

グラフは無向であるので1番のグラフからM秒でいける牧場を列挙すればよい。
ダイクストラ法を用いるのが適当。

ソースコード

int f,p,c,m,cow[501];
vector<vector<pi> > e;
bool v[501];

int main()
{
	scanf("%d%d%d%d",&f,&p,&c,&m);
	e.resize(f+1);
	
	rep(i,p)
	{
		int a,b,d; scanf("%d%d%d",&a,&b,&d);
		e[a].pb(mp(b,d)); e[b].pb(mp(a,d));
	}
	rep(i,c)scanf("%d",cow+i);
	
	priority_queue<pi> Q; Q.push(mp(0,1));
	while(!Q.empty())
	{
		int c=Q.top().second,cc=-Q.top().first; Q.pop();
		
		if(v[c])continue;
		v[c]=1;
		fr(i,e[c])if(!v[i->first])
		{
			if(cc+i->second>m)continue;
			Q.push(mp(-cc-i->second,i->first));
		}
	}
	
	int cnt=0,ans[501];
	rep(i,c)if(v[cow[i]])ans[cnt++]=i+1;
	printf("%d\n",cnt);
	rep(i,cnt)printf("%d\n",ans[i]);
	
	return 0;
}

2376 Cleaning Shifts

問題概要

N頭の牛から掃除当番を選出する。
T秒の間、どの秒にも掃除当番が最低一人以上いなければならない。

各牛が掃除する時間は、a[i],b[i]で指定される。
このとき、条件を満たすために最低限必要な牛の数を求めよ。

N≦25000,T≦1,000,000を満たす。

解法

各牛の、掃除の開始時間でソートする。

その後、開始時間が1の牛で、終了時間が最も遅い牛を選ぶ。
開始時間が、「今まで掃除し終わった時間」以下の牛で、掃除終了時間が最も遅い牛を選ぶ。その牛に掃除させる。
これを繰り返せばよい。

ソースコード

int n,t;
pi in[25000];

int main()
{
	scanf("%d%d",&n,&t);
	rep(i,n)
	{
		int a,b; scanf("%d%d",&a,&b);
		in[i]=mp(a,b);
	}
	sort(in,in+n);
	
	int cv=0,mx,cur=0,ans=0;
	for(;cur<n&&cv<t;)
	{
		mx=0;
		for(;cur<n&&in[cur].first<=cv+1;cur++)mx=max(mx,in[cur].second);
		if(mx==0)break;
		cv=mx; ans++;
	}
	printf("%d\n",cv==t?ans:-1);
	
	return 0;
}