Indeedなう（本選B） : D - Game on a Grid

今回の問題では一番おもしろかったです。
http://indeednow-finalb-open.contest.atcoder.jp/tasks/indeednow_2015_finalb_d

問題

H*Wのグリッドがあり、各セルにはそれぞれ非負整数P(x,y)が振られている。
プレイヤーは最初セル(sx,sy)に降り立った後、隣接マスを辿って(gx,gy)に移動したい。

あるセル(x,y)に初めて到達すると、P(x,y)の他、直前にいたマスの整数とP(x,y)の積の分得点が得られる。
同じセルを何度移動しても良く、(gx,gy)を通過してもゴールしなくても良い。
得られる総得点の最大値を求めよ。

解法

P(x,y)は非負なので、全セル通るとよい。
よって、P(x,y)の総和分の得点は確実に得られる。

問題は、隣接マスとの積の処理である。
ここで良く考えるとこの問題は全域木を求める問題に帰着できることがわかる。
ただし、通常最小全域木を考える代わりに得点の最大値を求めるようになっている。

ここまでわかれば、最小全域木のコスト判定を大小逆にして処理するだけ。

class UF {
	public:
	int um;
	vector<int> ufpar,ufrank,ufcnt;
	UF(int um_=100002) { um=um_; ufrank=vector<int>(um,0); ufcnt=vector<int>(um,1); for(int i=0;i<um;i++) ufpar.push_back(i);}
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int H,W;
int sy,sx,gy,gx;
ll tot;
ll P[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	cin>>sx>>sy>>gx>>gy;
	sx--; sy--;
	FOR(y,H) {
		FOR(x,W) cin>>P[y][x], tot+=P[y][x];
	}
	
	priority_queue<pair<ll,int> > Q;
	FOR(y,H) {
		FOR(x,W) {
			if(y<H-1) Q.push(make_pair(P[y][x]*P[y+1][x],(y+1)*1000000+x*10000+y*100+x));
			if(x<W-1) Q.push(make_pair(P[y][x]*P[y][x+1],y*1000000+(x+1)*10000+y*100+x));
		}
	}
	
	UF uf;
	while(Q.size()) {
		auto e=Q.top();
		Q.pop();
		x=e.second/10000,y=e.second%10000;
		if(uf[x]==uf[y]) continue;
		uf.unite(x,y);
		tot+=e.first;
	}
	
	cout<<tot<<endl;
}

まとめ

全域木と気づくと簡単。