「メンバー/SGHR/topcoder/PowerOutage」の編集履歴（バックアップ）一覧はこちら

「メンバー/SGHR/topcoder/PowerOutage」(2014/06/06 (金) 18:38:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*[[問題>http://community.topcoder.com/stat?c=problem_statement&pm=1697]]

*ジャンル
Graph Theory

*解説
ループのないグラフが与えられ、すべてのノードを回る最小コストの経路を求めよ、という問題。
深さ優先探索で解く。

*コード
#highlight(C++,linenumber){{
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;

#define MAX_V 50

class PowerOutage {
public:
  vector< vector< pair<int, int> > > connect;

  int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
    connect.resize(MAX_V);
    for(int i=0; i<fromJunction.size(); i++){
      connect[fromJunction[i]].push_back(make_pair(toJunction[i], ductLength[i]));
    }
    return dfs(0);
  }

  int nodecost(int i){
    int c = 0;
    for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
      c += it->second + nodecost(it->first);
    }
    return c;
  }

  int dfs(int i){
    int min = 10000000;
    for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
      int c = 0;
      c += it->second + dfs(it->first);
      for(vector< pair<int,int> >::iterator jt = connect[i].begin(); jt != connect[i].end(); jt++){
	if(it != jt) c += 2*jt->second + 2*nodecost(jt->first);
      }
      min = min < c ? min : c;
    }
    if(min == 10000000) min = 0;
    return min;
  }
};
}}

*[[問題>http://community.topcoder.com/stat?c=problem_statement&pm=1697]]

*ジャンル
グラフ

*解説
ループのないグラフが与えられ、すべてのノードを回る最小コストの経路を求めよ、という問題。
深さ優先探索で解く。

*コード
#highlight(C++,linenumber){{
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;

#define MAX_V 50

class PowerOutage {
public:
  vector< vector< pair<int, int> > > connect;

  int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength) {
    connect.resize(MAX_V);
    for(int i=0; i<fromJunction.size(); i++){
      connect[fromJunction[i]].push_back(make_pair(toJunction[i], ductLength[i]));
    }
    return dfs(0);
  }

  int nodecost(int i){
    int c = 0;
    for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
      c += it->second + nodecost(it->first);
    }
    return c;
  }

  int dfs(int i){
    int min = 10000000;
    for(vector< pair<int,int> >::iterator it = connect[i].begin(); it != connect[i].end(); it++){
      int c = 0;
      c += it->second + dfs(it->first);
      for(vector< pair<int,int> >::iterator jt = connect[i].begin(); jt != connect[i].end(); jt++){
	if(it != jt) c += 2*jt->second + 2*nodecost(jt->first);
      }
      min = min < c ? min : c;
    }
    if(min == 10000000) min = 0;
    return min;
  }
};
}}