SRM Div1 easy : BiconnectedDiv1

問題概要 :

n個のノードが存在し、それらは0からn-1まで番号が割り振られている

ノードiはi+1がn-1以下であればノードi+1に向けて重みw1[i]の辺を持つ

また、ノードiはi+2がn-1以下であればノードi+2に向けて重みw2[i]の辺を持つ

各辺は無向辺である

このようにして構成されるグラフから何本か辺を削除する

ただし、辺を削除した後はそのグラフの任意の異なる２頂点u,v間にパスが存在する必要がある

（つまり、uからvに残っている辺をたどって移動できる必要がある)

上の制約を満たした上で0本以上辺を削除したとき、残った辺の重みの総和の最小値を求めよ

解法 :

動的計画法で解いた

まず、辺を消した後に条件を満たすようなグラフがどのようなものなのかを考える
これは全てのノードが１つの閉路に含まれるグラフである
このようなグラフであれば、どこを消しても少なくとも１本はパスが存在する
全てのノードが１つの閉路に属していない場合、閉路に属していないノードから出ている辺を削除すると連結でなくなる

グラフ全体が１つの閉路になるための条件は各ノードの次数が2以上で連結であることである
（グラフが閉路かどうかの判定は各ノードの次数が偶数で連結であること　今回は閉路+αがあっても良いので2以上にした）
あとは各ノードの次数が2未満にならないように辺を削除するかしないかでDPをする

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;

struct Edge {
  int dst,w;
};

#define MAX 300
vector<Edge> G[MAX];
int dp[MAX];

class BiconnectedDiv1 {
public:
  int V;
  int minimize( vector <int> w1, vector <int> w2 ) {
    V = (int)w1.size() + 1;
    rep(i,MAX) G[i].clear();
    memset(dp,0,sizeof dp);
    int sum = 0;
    rep(i,(int)w1.size()) {
      G[i].push_back((Edge){i+1,w1[i]});
      G[i+1].push_back((Edge){i,w1[i]});
      sum += w1[i];
    }
    rep(i,(int)w2.size()) {
      G[i].push_back((Edge){i+2,w2[i]});
      G[i+2].push_back((Edge){i,w2[i]});
      sum += w2[i];
    }
    int maxi = 0;
    REP(v,1,V-1) {
      dp[v] = max(dp[v],dp[v-1]);
      if( (int)G[v].size() >= 3 ) {
        rep(i,(int)G[v].size()) {
          Edge &e = G[v][i];
          if( v > e.dst ) continue;
          if( (int)G[e.dst].size() < 3 ) continue;
          dp[e.dst] = max(dp[e.dst],dp[v]+e.w);
          maxi = max(maxi,dp[e.dst]);
        }
      }
    }
    return sum - maxi;
  }
};