SRM 693 div2 medium BiconnectedDiv2

問題

問題概要

グラフはi - i+1　と i - i+2　を結ぶ２つ辺が貼られている。 二重連結グラフの状態を保ったまま辺を取り除き、辺のコストを最小にしたときの辺のコストの合計を求める。

解法

biconnected graph(2重連結グラフ)とは、任意の頂点を1つ取り除いても、グラフが連結のままであるグラフである。今回の問題で考察してみると、i - i+2の辺はすべて必要であることがわかる。これは、頂点iを削除したとき、i-1 - i と　i - i+1　の辺も削除されることになる。このときに、i-1　- i+1　の辺がないと、iを挟んで左から右へ右から左へ移動することができるなくなってしまうので、必ず必要ということになる。 また、w1の両サイトの辺も必要である。これはiを削除した場合、i - i-2　と i - i+2　の辺もなくなるので、i-2とi-1を連結にしようとした場合、w1の中で、1-2の辺だけは少なくともないといけないことがわかる。同様にn-1 - n　も必要ということになる。
まとめると、少なくとも必要なのは、w1の両サイドの2辺と、w2のすべての辺。そして、辺のコストの最小値を求めるので、残りのw1の中でコストが負のものは利用したほうが良い。
図

srm 693 div2 medium

ミス

すごく悩んだ。

コード

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

class BiconnectedDiv2{
public:
    int minimize(vector <int> w1, vector <int> w2){
        //必ず必要な辺はw1の両端とw2全部
        int ans = 0;
        ans = w1[0] + w1[w1.size() - 1];
        for (int i = 0; i < w2.size(); ++i){
            ans += w2[i];
        }

        //マイナスなら合計が小さくなるので使う
        for (int i = 1; i < w1.size() - 1; ++i){
            if(w1[i] < 0){
                ans += w1[i];
            }
        }
        return ans;
    }
};