Saiko~ No Contesuto #02 Waiwai Otaku Panic

問題

Programming Problems and Competitions :: HackerRank

解法

まず, 最短経路に含まれる辺以外は取り除きます。

また, 頂点 0 からの距離が別のものは, 絶対に通る辺が被ることはありません(被るとすると, 距離が近い方の頂点はどこか寄り道してることになるので)。

ということで, 頂点 0 からの距離ごとに, 頂点 0 に向かう経路が配列 A の分確保されているかをチェックしていけば良いです。最大フローを使いますが, 以下のようにします。

・まず, 最短経路に含まれる有向辺を追加(無向辺じゃないですよ)
・頂点 s を追加。頂点 0 からの距離が dist のものについて経路が確保されているか調べたい場合, 距離が dist の頂点それぞれに, 対応する A[i] の容量の辺を s から i に引く

で, 最大フローが対応する A[i] の和になっていれば良いです。

得た知見

• 最短経路系, 初手で最短経路に含まれる辺以外取り除く処理が多い気がする
  • フロー流す時無向辺じゃなくて有向辺にしなきゃダメだった点も注意だった

// Dinic法:最小カット,最大フローで使う
// 使い方: Dinic* dinic = new Dinic(V)で初期化(Vは頂点数)
// dinic->add_edgeまたはdinic->add_edge_bothで点をつなげてdinic->max_flowで最大フローを求める
#define NG -1
#define SZ(a) ((int)((a).size()))
class Dinic
{
public:
    Dinic(int input_maxv) : maxv(input_maxv)
    {
        G.resize(input_maxv);
        level.resize(input_maxv);
        iter.resize(input_maxv);
    }

    void add_edge_both(int from, int to, int cap)
    {
        const int rev_from  = SZ(G[from]);
        const int rev_to    = SZ(G[to]);
        G[from].push_back(edge(to,cap,rev_to));
        G[to].push_back(edge(from,cap,rev_from));
    }

    void add_edge(int from, int to, int cap)
    {
        const int rev_from  = SZ(G[from]);
        const int rev_to    = SZ(G[to]);
        G[from].push_back(edge(to,cap,rev_to));
        G[to].push_back(edge(from,0,rev_from));
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        for(;;)
        {
            bfs(s);
            if(level[t]<0) break;
            fill(iter.begin(),iter.end(),0);
            int f;
            while( (f=dfs(s,t,DINIC_INF))>0)
            {
                flow += f;
            }
        }

        return flow;
    }

    vector <bool> get_nodes_in_group(int s)
    {
        vector <bool> ret(maxv);

        queue<int> que;
        que.push(s);
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            ret[v]=true;

            for(int i=0;i<SZ(G[v]);i++)
            {
                edge &e = G[v][i];
                if(e.cap>0 && !ret[e.to])
                {
                    que.push(e.to);
                }
            }
        }
        return ret;
    }

    void disp()
    {
        for (int v = 0; v < maxv; v++)
        {
            printf("%d:",v);
            for(int i=0;i<SZ(G[v]);i++)
            {
                if(G[v][i].init_cap>0)
                {
                    printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
                }
            }
            printf("\n");
        }
    }

private:
    void bfs(int s)
    {
        fill(level.begin(),level.end(),NG);
        queue<int> que;
        level[s]=0;
        que.push(s);
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            for(int i=0;i<SZ(G[v]);i++)
            {
                edge &e = G[v][i];
                if(e.cap>0 && level[e.to]<0)
                {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f)
    {
        if(v==t) return f;
        for (int &i=iter[v];i<SZ(G[v]);i++)
        {
            edge& e = G[v][i];
            if(e.cap>0 && level[v]<level[e.to])
            {
                int d = dfs(e.to, t, min(f, e.cap));
                if(d>0)
                {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    static const int DINIC_INF = INT_MAX;

    struct edge
    {
        edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
        int to;
        int cap;
        int rev;
        int init_cap;
    };

    int maxv;
    vector < vector <edge> > G;
    vector < int > level;
    vector < int > iter;

};

struct edge {
    int v;
    ll w;
    bool used;
    edge() {}
    edge(int v, ll w) : v(v), w(w), used(false) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

const int MAXN = 111;
vector<vector<edge> > G;
int A[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 1; i < N; i++) {
        cin >> A[i];
    }
    G.resize(N);
    for (int i = 0; i < M; i++) {
        int f, t;
        cin >> f >> t;
        f--; t--;
        G[f].emplace_back(t, 1);
        G[t].emplace_back(f, 1);
    }
    auto d = dijkstra(N, G, 0);
    for (int i = 0; i < N; i++) {
        for (edge& e : G[i]) {
            if (d[e.v]-d[i] == -1) {
                e.used = true;
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        vector<int> vs;
        for (int j = 0; j < N; j++) {
            if (d[j] == i) vs.push_back(j);
        }
        if (vs.size() == 0) continue;
        int s = N+1;
        Dinic dinic(s+1);
        for (int j = 0; j < N; j++) {
            for (edge e : G[j]) {
                if (e.used) {
                    dinic.add_edge(j, e.v, 1);
                }
            }
        }
        int sum = 0;
        for (int el : vs) {
            dinic.add_edge(s, el, A[el]);
            sum += A[el];
        }
        if (sum == 0) continue;
        if (sum > dinic.max_flow(s, 0)) {
            cout << "PANIC" << endl;
            return 0;
        }
    }
    cout << "NO PANIC" << endl;
    return 0;
}