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]; } };