東京工業大学プログラミングコンテスト 2015 N 何かグラフの問題 牛ゲー

##問題
https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_n
##見た感じ
線形な不等式を満たすような$a_i$が存在する最小の$T$を見つける問題で、この線形な不等式を以下のように変形することで、いわゆる***牛ゲー***として解けそう。

```math
e={u\rightarrow v}に対して\\
a_u \leq a_v + (T-c_e)~~~~(a_u , a_v is~not~fixed)\\
z \leq a_v + (T-c_e - a_u)~~~~(only~a_u is~fixed)\\
a_u \leq z + (T-c_e + a_v)~~~~(only~a_v is~fixed)\\
z\leq z+(T+a_v-c_e-a_u)~~~~(both are fixed)
```
ここで$z$は$z=0$なる解がなければ元の不等式を満たす解はないことを表す新たなパラメータ。
ここで、$T$は単調なはずで、もし$T=t_0$で上の不等式をみたす解が存在すれば、それは$T=t_1~~(t_0\leq t_1)$の場合の解でもあるので、最小の$T_{opt}$について、$T<T_{opt}$の時解は存在せず、$T_{opt}\leq T$のとき必ず解が存在する。
また、上の不等式の問題をグラフの最短路問題だと解釈すると、解が存在するかどうかは負閉路が存在するか否かに対応していて、それは$T$が十分小さくて辺の重みがすべて負やったら、それをそれ以上小さくしても解が存在しないのには変わりはなくて、逆に$T$が十分おおきくて、辺の重みがすべて正やったら、それ以上大きくしても、解が存在することには変わりはないので、$-10^9\leq a_i \leq 10^9$よりちょっと多めにしても$-10^{15}\leq T \leq 10^{15}$の中に最小値は存在して、ここになければ、最小値がない場合としてもよさそう。
なので、まず最小値がない場合を調べるため、$T=-10^{15}$の場合を計算して、負閉路があれば'#'を返す。
そうじゃなければ、もとの区間でTを0からスタートして、上の不等式から導かれる最短路問題をBellman-Fordで解いて、負閉路があれば$T$を大きく、なければ小さくしていく。
これを2分探索でやれば$O(NM\log{10^{15}})$で十分間に合う
##解法
上のやり方でBellman-Fordするときに、グラフが連結とは限らないので、unionfind木で連結成分を調べておいて、各連結成分に一つ初期値０のノードがあるようにした。
##ソースコード
```c++
struct uftree{
    int cou;
    vector<int> parent;
    vector<int> rank;
    vector<int> _size;
    uftree(int n){
        init(n);
    }
    void init(const int &n){
        parent=vector<int>(n);
        rank=vector<int>(n,0);
        _size=vector<int>(n,1);
        cou=n;
        rep(i,n){
            parent[i]=i;
        }
    }
    int root(const int &i){
        return parent[i]==i?i:parent[i]=root(parent[i]);
    }
    bool same(const int &i,const int &j){
        return root(i)==root(j);
    }
    void merge(int i,int j){
        i=root(i);j=root(j);
        if(i==j)return;
        cou--;
        if(rank[i]>=rank[j]){
            parent[j]=i;
            _size[i]+=_size[j];
        }else{
            parent[i]=j;
            _size[j]+=_size[i];
        }
        if(rank[i]==rank[j])rank[i]++;
        return;
    }
    int count(){
        return cou;
    }
    int unitsize(const int &i){
        return _size[root(i)];
    }
};
const int N_MAX=2005;
ll n,m,k,mt;
vll a(N_MAX);
vector<double> d;
double t=-INF15;
vector<bool> mem(N_MAX);
edges v;
uftree tree(N_MAX);

void Main(){
    int x=0,y=INF10,z=1;
    //入力
    cin>>n>>m>>k;
    rep(i,k){
        cin>>x>>y;
        a[x]=y;
        mem[x]=1;
    }
    rep(i,m){
        cin>>x>>y>>z;
        if(!mem[x]&&!mem[y])v.pb(edge(y,x,-z)),tree.same(y,x);
        else if (mem[x]&&!mem[y])v.pb(edge(y,0,-z-a[x])),tree.same(y,0);
        else if(!mem[x]&&mem[y])v.pb(edge(0,x,a[y]-z)),tree.same(0,x);
        else v.pb(edge(0,0,a[y]-a[x]-z));
    }
    //処理
    a.clear();
    a.pb(0);
    rep1(i,n){
        if(i==tree.root(i)&&!tree.same(0,i))a.pb(i);
    }
    bool tof=false,check=true;
    d.resize(n+1,INF18);
    arep(b,a)d[b]=0;
    rep(i,n){
        bool sw=false;
        arep(w,v){
            if(d[w.from]!=INF18&&minin(d[w.to],d[w.from]+w.cost+t)){
                sw=true;
            }
        }
        if(!sw)break;
        if(i==n-1){
            tof=true;
        }
    }
    if(!tof){
        cout << "#" <<endl;
        return;
    }
    double up=INF15,down=-INF15;
    t=0;
    while(check){
        tof=true;
        d.resize(n+1,INF18);
        arep(b,a)d[b]=0;
        rep(i,n){
            bool sw=false;
            arep(w,v){
                if(d[w.from]!=INF18&&minin(d[w.to],d[w.from]+w.cost+t)){
                    sw=true;
                }
            }
            if(!sw)break;
            if(i==n-1){
                tof=false;
            }
        }
        if(!tof){
            down=t;
            t=(t+up)/2;
        }else{
            up=t;
            t=(t+down)/2;
        }
        if(abs(up-t)<EPS)check=false;
    }
    //出力
    cout << t <<endl;
}

int main(){
    cin.tie(nullptr);
    cout<<fixed<<setprecision(12);
    Main();
}
```