読者です 読者をやめる 読者になる 読者になる

SRM626 Med

問題:NegativeGraphDiv1
概要:
頂点数n(<=50)の有向グラフがあって、辺(2500個以下)は整数の重み(0<=重み<=1e5)付きで、多重辺,self loopもある.今頂点0からn-1に行きたいが、charges(<=1e9)回だけ重みを負にしてその辺を渡ることが出来る(渡った後は重みは元に戻る).n-1までの経路でコスト最小はいくらか?(charges回全て使い切らなくても良い,途中でn-1を通っても良い)
解法:
chargesがでかいので、上手く割り振ったりするのはむずそう,ダブリング?重みを負に出来る回数k回とj回のデータからk+j回のデータがほしい.
a->bに1回以下使って行くときのコスト最小を行列で持つ
合成演算は掛け算ではないが、掛け算時のそれぞれの項のminをとればよい

ポイント:
今あるグラフの辺を使って、新しくグラフを作る
行列累乗は、別に掛け算じゃなくても結合法則が成り立つ演算のn乗ならできる

コード:

#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vv;
struct edge{int from,to,cost;};
vector<ll> G[50];
vector<edge> es;
ll dis[50][50],inf=1e17;
vv A(50,vi(50));
class NegativeGraphDiv1{
	public:
	vv cal(vv x,vv y,int n){
		vv z(50,vi(50,inf));
		rep(i,n) rep(j,n) rep(k,n) z[i][j]=min(z[i][j],x[i][k]+y[k][j]);
		return z;
	}
	long long findMin(int n, vector <int> from, vector <int> to, vector <int> weight, int c){
		int m=from.size();
		rep(i,n) rep(j,n) if(i!=j) dis[i][j]=inf,A[i][j]=inf;
		rep(i,m) dis[from[i]-1][to[i]-1]=min(dis[from[i]-1][to[i]-1],(ll)weight[i]);
		rep(i,n) rep(j,n) rep(k,n) dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
		if(c==0) return dis[0][n-1];
		rep(i,m) rep(j,n) rep(k,n) A[j][k]=min(A[j][k],dis[j][from[i]-1]-weight[i]+dis[to[i]-1][k]);
		vv mat=A,now=A;
		c--;
		for(int i=0;(1<<i)<=c;i++){
			if(c&(1<<i)) now=cal(now,mat,n);
			mat=cal(mat,mat,n);
		}
		return now[0][n-1];
	}
};