AOJ 2605 : Social Monsters

問題リンク : Social Monsters | Aizu Online Judge

問題概要 :
N匹のモンスターがいる
その中からK匹を選んでチームを作る
任意の2匹のモンスター間には仲良し度があり
仲良し度が0の場合、それらのモンスターを一緒にチームに入れることはできない
それ以外の場合、それらのモンスターを一緒にチームに入れることでその仲良し度と同じだけの力を得る
仲良し度のペアがM個与えられる
M個のペア以外のペアの仲良し度は全てチーム入れることはできるが力は得られない
あるモンスターがM個のペアの中に現れる回数は高々２回である
得られる力の最大値を求めよ

解法 :
DP

モンスターをノード、仲良し関係をエッジとしグラフを作成すると
制約からそのグラフは線か円か点のいずれかになる
（１つのノードから辺が高々２回しかでないようなとき、そのグラフは円か線になる　割と頻繁に出てくる制約なので覚えておこう）

まず、UnionFindで連結な成分毎に分ける
その後DFSで各成分をvectorにまとめる
後はDPで最大値を計算する

dp1[i][j][k][l] := i番目のノードまででj個選び、i番目のノードを選んだかどうか ( k で true, false )、0番目のノードを選んだかどうか ( l で true, false ) という状態の最大値

どの成分かは配列には持たない ( 持てない ) のでループである成分について最大値を計算したらすぐに使ってしまうようにする

dp2[i] := i個選んだときの最大値

コード:

#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;
 
const int IINF = INT_MAX;
struct Edge { int src,dst,weight; };
 
typedef pair<bool,vector<Edge> > boolVectorEdge; // false -> sen, true -> en
typedef pair<int,int> ii;
 
int N,M,K,par[2010],edge_cnt[2010];
vector<int> ver[2010];
vector<boolVectorEdge> graphs;
vector<Edge> edges;
vector<Edge> G[2010];
bool used[2010];
map<ii,int> costs;
 
int find(int i){
  if( i == par[i] ) return i;
  return par[i] = find(par[i]);
}
 
void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}
 
void dfs(int prev,int cur,int index,vector<Edge>& graph){
  int cnt = 0,cnt_sub=0;
  rep(i,G[cur].size()){
    int next = G[cur][i].dst;
    if( next == prev ) continue;
    ++cnt_sub;
    if( cnt_sub == 2 ) {
      assert(used[next]);
      assert( costs.count(ii(cur,next)) );
      graph.push_back((Edge){(int)graph.size()-1,0,costs[ii(cur,next)]});
    }
    if( !used[next] ) { // en no baai mo aru node
      ++cnt;
      used[next] = true;
      assert( costs.count(ii(cur,next)) );
      graph.push_back((Edge){index-1,index,costs[ii(cur,next)]});
      dfs(cur,next,index+1,graph);
    }
  }
  assert( cnt <= 1 );
}
 
void makeGraphs(){
  rep(i,N) par[i] = i;  
  rep(i,M) unit(edges[i].src,edges[i].dst);
  rep(i,N) ver[find(i)].push_back(i);
  rep(i,M) ++edge_cnt[find(edges[i].src)];
  rep(i,2010) if( ver[i].size() ){
    memset(used,false,sizeof(false));
    boolVectorEdge graph;
    graph.first = ( (int)ver[i].size() == edge_cnt[i] ) ;
    int sp = ver[i][0];
    if( !graph.first ) rep(j,ver[i].size()) if( G[ver[i][j]].size() == 1 ) { sp = ver[i][j]; break; }
    graph.second.push_back((Edge){0,0,-IINF});
    used[sp] = true;    
    dfs(-1,sp,1,graph.second);
    graphs.push_back(graph);
  }
  /*
    rep(i,graphs.size()) {
    cout << ((graphs[i].first)?"circle":"segment") << endl;
    rep(j,graphs[i].second.size()) {
    cout << "(" << graphs[i].second[j].src << "," << graphs[i].second[j].dst << ":" << graphs[i].second[j].weight << ") " ;
    } 
    puts("");
    puts("");
    }
  */
}
 
int dp1[2010][2010][2][2]; 
//int dp2[2010][2010]; 
int dp2[2010]; // improved
int maxi[2010];
 
void compute(){
  makeGraphs();
  int V = graphs.size();
  //rep(i,V+1) rep(j,K+1) dp2[i][j] = -IINF;
  //dp2[0][0] = 0;
  rep(i,K+1) dp2[i] = -IINF;
  dp2[0] = 0;
   
  rep(_,V){
    bool type = graphs[_].first;
    vector<Edge> &G = graphs[_].second;
    rep(i,G.size()+1) rep(j,K+1) rep(k,2) rep(l,2) dp1[i][j][k][l] = -IINF;
    rep(j,2) dp1[0][j][j][j] = 0;
    rep(i,(int)G.size()-1-(type?1:0)){
      rep(j,K+1){
        rep(k,2){
          rep(l,2) if( dp1[i][j][k][l] != -IINF ) {
 
            if( type && i == (int)G.size()-3 ) {
              if( k ) {
                // cur use next use
                if( !( ( l && G[i+2].weight == 0 ) || G[i+1].weight == 0 ) ) {
                  int cost = G[i+1].weight;
                  if( l ) cost += G[i+2].weight;
                  dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]+cost);
                }
                // cur use next dont use
                dp1[i+1][j][0][l] = max(dp1[i+1][j][0][l],dp1[i][j][k][l]);
              } else {
                // cur dont use next use
                if( !( l && G[i+2].weight == 0 ) ) {
                  dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]+(l?G[i+2].weight:0));
                }
                // cur dont use next dont use
                dp1[i+1][j][0][l] = max(dp1[i+1][j][0][l],dp1[i][j][k][l]);
              }
              continue;
            } else {
              // use
              if( k ) {
                if( j+1 <= K && G[i+1].weight != 0 ) {
                  dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]+G[i+1].weight);
                }
              } else {
                if( j+1 <= K ) {
                  dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]);
                }
              }
            }
            // dont use
          INVALID:;
            dp1[i+1][j][0][l] = max(dp1[i+1][j][0][l],dp1[i][j][k][l]);
          }
        }
      }
    }
 
    rep(i,K+1) maxi[i] = -IINF;
    rep(j,K+1) rep(k,2) rep(l,2) maxi[j] = max(maxi[j],dp1[(int)G.size()-1-(type?1:0)][j][k][l]);
     
    for(int j=K;j>=0;j--) if( dp2[j] != -IINF ) {
        for(int k=0;k<=G.size()&&j+k<=K;k++) if( maxi[k] != -IINF) {
          dp2[j+k] = max(dp2[j+k],dp2[j]+maxi[k]);
        }
    }
  }
  if( dp2[K] == -IINF ) puts("Impossible");
  else printf("%d\n",dp2[K]);
}
 
int main(){
  scanf("%d %d %d",&N,&M,&K);
  {
    int a,b,c;
    rep(_,M) {
      scanf("%d %d %d",&a,&b,&c);
      --a, --b;
      if( a > b ) swap(a,b);
      costs[ii(a,b)] = costs[ii(b,a)] = c;
      G[a].push_back((Edge){a,b,c});
      G[b].push_back((Edge){b,a,c});
      edges.push_back((Edge){a,b,c});      
    }
  }
  compute();
  return 0;
}