PKU演習問メモ(6/17) - simezi

No.	問題名	問題の種類および解法	難易度
2377	Bad Cowtractors	最小全域木	★★☆☆☆
2606	Rabbit hunt	直線の平行判定	★☆☆☆☆
2810	Take Your Vitamins	文字列	★☆☆☆☆
3255	Roadblocks	k-最短路	★★★☆☆

2377 Bad Cowtractors

問題概要

1番からN番のN個の牧場があり、牧場同士のネットワークを敷設するのにかかる費用のリストが

a b c

の形式でM個与えられる。ただしこれは牧場aと牧場bをcのコストで結ぶことができるという意味である。
このとき、全ての牧場を結ぶ閉路のないネットワークで、もっとも費用のかかるようなものを作るのにかかる費用を求めよ。

解法

エッジの重みをすべて負にしてプリム法。
すると本問の答えである最小全域木ならぬ最大全域木が求められる。

ソースコード

int main()
{
	int n,m; scanf("%d%d",&n,&m);
	vector<vector<pi> > e(n);
	rep(i,m)
	{
		int a,b,c; scanf("%d%d%d",&a,&b,&c); a--,b--;
		e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
	}
	
	int vis=0,cost=0;
	bool v[n]; fill_n(v,n,0);
	
	priority_queue<pi> Q; Q.push(mp(0,0));
	while(!Q.empty())
	{
		int c=Q.top().second,cc=Q.top().first; Q.pop();
		
		if(v[c])continue;
		v[c]=1; vis++; cost+=cc;
		if(vis==n)
		{
			cout<<cost<<endl; return 0;
		}
		
		fr(it,e[c])if(!v[it->first])
		Q.push(mp(it->second,it->first));
	}
	cout<<-1<<endl;
	
	return 0;
}

2606 Rabbit hunt

問題概要

平面上のn個の点の座標が与えられる。このとき一直線上に並んでいる点の数の個数の最大値を求めよ。

n≦200であり、任意の二点が同一であることはない。

解法

二点を通る直線を引き、残りのn-2点からその直線状に乗る点を数えるO(n^3)の解法で間に合う。

ソースコード

P p[200];

int crs(P a,P b)
{
	return a.real()*b.imag()-a.imag()*b.real();
}

int main()
{
	int n,ans=2; cin>>n;
	rep(i,n)cin>>p[i].real()>>p[i].imag();
	
	rep(i,n)rep(j,i)
	{
		int cnt=2;
		rep(k,n)if(k!=i&&k!=j&&crs(p[i]-p[j],p[k]-p[j])==0)cnt++;
		ans=max(ans,cnt);
	}
	cout<<ans<<endl;
	
	return 0;
}

2810 Take Your Vitamins

問題概要

ビタミン・ミネラルの摂取量が以下の形式で与えられる。
A U R V

A: ビタミン・ミネラルの摂取量
U: 単位（空白文字を含まない）
R: ビタミン・ミネラルの必要量
V: ビタミン・ミネラルの名称（空白文字を含みうる）

入力データの終了はAが負のダミーにより与えられる。

このとき、摂取量が1%以上のものは以下の形式で出力し、
V A U P%

P: 必要量に対する摂取量の割合(百分率）

摂取量が1%に満たないものについては、1%以上のビタミン・ミネラルを全て出力した後に
"Provides no significant amount of:"を出力し、
続けて1行に一つずつその名称を出力せよ。

解法

空白文字や、"1%"という判定に気をつけて実装する。
1%を、切り捨てて0%になるかどうかなどと実装しないよう注意……

ソースコード

int main()
{
	double a,r; string u,v;
	vector<string> nosig;
	
	while(1)
	{
		cin>>a>>u>>r; cin.ignore();
		getline(cin,v);
		if(*v.rbegin()==' ')v.erase(v.end()-1,v.end());
		
		if(a<0)break;
		
		double p=a*100/r;
		if(p<1)
		{
			nosig.pb(v); continue;
		}
		
		printf("%s %.1f %s %.0f%%\n",v.c_str(),a,u.c_str(),p);
	}
	puts("Provides no significant amount of:");
	fr(it,nosig)puts(it->c_str());
	
	return 0;
}

3255 Roadblocks

問題概要

n個の都市と、それらを結ぶ双方向に通行可能なr本の道路がある。
いま。都市1から都市nまで「二番目に短い経路」を通って行きたい。
そのような経路の長さを求めよ。

ただし、一番短い経路が複数あるとき、二番目に短い経路とはそれらの次に短い経路のことを言うものとする。
n≦5000,R≦100000である。

解法

ダイクストラ法においてn番目のノードの最短距離を持つ配列を2個に多重化し、2番目までに短い距離をもっておく。
http://www.prefield.com/algorithm/graph/k_shortest_paths.htmlに詳しい解説がある。

ソースコード

int n,r;
vector<vector<pi> > e;

int solve()
{
	vi dist[n];
	priority_queue<pi> Q; Q.push(mp(0,0));
	while(!Q.empty())
	{
		int c=Q.top().second, cc=Q.top().first; Q.pop();
		//if(dist[c].size()>=2)continue;//これでは間違いだが、何故かPKUではAC.下が正しい
		if(dist[c].size()>=2||dist[c].size()==1&&dist[c][0]==cc)
		  continue;
		dist[c].pb(cc);
		fr(it,e[c])Q.push(mp(cc-it->second,it->first));
	}
	return dist[n-1].size()>=2?-dist[n-1][1]:-1;
}

int main()
{
	scanf("%d%d",&n,&r);
	e.resize(n);
	
	rep(i,r)
	{
		int a,b,c; scanf("%d%d%d",&a,&b,&c); a--,b--;
		e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
	}
	cout<<solve()<<endl;
	
	return 0;
}