SRM 446 DIV1 Medium AntOnGraph

SRM グラフ 行列 C++

http://apps.topcoder.com/stat?c=problem_statement&pm=10516&rd=13900

問題

重み付き有向グラフ(V <= 50, -499 <= w <= 499)がある。
今、点0に蟻が居る。
蟻は1秒間にstepsPerSecond(<=100)回動き続けて(その場に立ち止まることはできない)
最大timeLimit(<=10^9)秒間動くことが出来る(秒の境目なら動くのをやめることができる)
蟻は最終的に点1に行きたい。
ここで、蟻が通った辺の重みの合計を最大化したい。
もし点1にたどり着くことができないのなら"IMPOSSIBLE"と返せ

回答

他の人の回答を参考にして、考えて、わかった。
まず、蟻が1回動くことは、その時点での全点間の最大重み(全点間最短距離と上下を入れ替えれば同じ、以下最大としてを考える)を求めればいい。これにはWarshall-Floyd法が使える。
ただし、このままではtimeLimit(<=10^9)が明らかに大きすぎる。
ここで、Warshall-Floyd法が行列の乗算と似た構造を持っていることに注目する。
実際に行列の乗算の、(+)をmaxに、(*)を(+)に変えたものがWarshall-Floydっぽくなる。
蟻が何回か動くことは行列の累乗として考えられる。
また、(-∞, max, (+))を利用すると半環になっていて、また、その行列も累乗の高速化アルゴリズム(バイナリ法)が使える構造になっている(詳細はよくわかって/調べてないが)
そのため、バイナリ法を使ってO(V^3 (log stepsPerSecond + log timeLimit))くらいで出来る。
後はtimeLimit以下、ということの扱いだが、これは一旦stepsPerSecond乗を計算した後、いつでも点1にとどまれるように、1→1のコスト0の辺を追加してやればいい。ただし、点1を含む負閉路(この場合は正閉路)があればその方が良いので、単に今の1→1のweightがマイナスの時のみ0にしてやればいい

コード
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(r,v) typeof(v) r = (v)
#define each(it,o) for(aut(it,o.begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii;

typedef ll Number;	//base
struct MaxPlus {
	Number t; struct MinusInf_tag {};
	explicit MaxPlus(Number x):t(x){}
	explicit MaxPlus(MinusInf_tag):t(-INF){}
	MaxPlus() {}
	inline bool isMinInf() const {return t==-INF;}
	MaxPlus operator+(const MaxPlus& y) const {
		if(isMinInf())return y;
		else if(y.isMinInf()) return *this;
		else return MaxPlus(max(t, y.t));
	}
	MaxPlus operator*(const MaxPlus& y) const {
		if(isMinInf() || y.isMinInf()) return MaxPlus(MaxPlus::MinusInf_tag());
		else return MaxPlus(t + y.t);
	}
};

typedef MaxPlus MatT; MatT Mat_zero = MaxPlus(MaxPlus::MinusInf_tag()), Mat_one = MaxPlus(0);
typedef vector<MatT> MatV;
typedef vector<MatV> Mat;

Mat mult(const Mat& A, const Mat& B) {
	int N = A.size();
	Mat C(N, MatV(N));
	rep(i, N) rep(j, N) {
		C[i][j] = Mat_zero;
		rep(k, A[i].size()) {
			C[i][j] = C[i][j] + A[i][k] * B[k][j];
		}
	}
	return C;
}

Mat ident(int N) {
	Mat A(N, MatV(N));
	rep(i, N) {
		rep(j, N) A[i][j] = Mat_zero;
		A[i][i] = Mat_one;
	}
	return A;
}
Mat power(const Mat& A, int p) {
	if(p == 0) return ident(A.size());
	else if(p == 1) return A;
	else {
		Mat B = power(mult(A, A), p >> 1);
		if(p & 1) B = mult(B, A);
		return B;
	}
}

struct AntOnGraph {
	string maximumBonus(vector <string> p0, vector <string> p1, vector <string> p2, int stepsPerSecond, int timeLimit) {
		int n = p0.size();
		Mat m(n, MatV(n));
		rep(i, n) rep(j, n) {
			string s;
			s += p0[i][j]; s += p1[i][j]; s += p2[i][j];
			if(s == "000") {
				m[i][j] = Mat_zero;
			}else {
				m[i][j] = MaxPlus(atoi(s.c_str()) - 500);
			}
			cout << "m["<<i<<"]["<<j<<"] = "<<m[i][j].t<<endl;
		}
		m = power(m, stepsPerSecond);
		//問題わかってなかったが、動く秒数はtimeLimit以下なら何秒でも良いため、
		//つまりその場に留まる辺を追加してあげる
		if(m[1][1].t < 0) m[1][1] = MaxPlus(0);
		m = power(m, timeLimit);
		if(m[0][1].isMinInf()) return "IMPOSSIBLE";
		stringstream s; s << m[0][1].t;
		return s.str();
	}
};