ichirin2501's diary

いっちりーん。

最小全域木の問題をすこし解いた

project euler 107
srm470::div2::hard
uva::11747::Heavy Cycle Edges


プリム法only...クラスカル法全く使ってねえ。
クラスカル法のほうが向いてる問題、ってのあるのかなぁ。
uva11747はちょっと実装が面倒だったけど、これってクラスカル法のほう向いてるのかな。
今度クラスカル法で書いてみよう。

project euler 107

やるだけ。

#include <略>
using namespace std;

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

#define sz 40

void pe_107(){
   int node[sz][sz];
   long long initsum = 0;
   rep(i,sz)rep(j,sz){
      scanf("%d",&node[i][j]);
      if( i<j && node[i][j]!=-1 )initsum += node[i][j];
   }
   
   bool vcheck[sz];
   vector<int> vn;
   rep(i,sz)vcheck[i]=false;
   vcheck[0]=true;
   vn.push_back(0);
   
   long long ans = 0;
   for(;;){
      int t_cost = 999999999, next_id=-1;
      rep(i,vn.size()){
         rep(j,sz)if( !vcheck[j] && node[vn[i]][j]!=-1 && t_cost>node[vn[i]][j] ){
            t_cost = node[vn[i]][j];
            next_id = j;
         }
      }
      if( next_id==-1 ) break;
      vn.push_back(next_id);
      vcheck[next_id] = true;
      ans += (long long)t_cost;
   }
   printf("%lld\n",initsum-ans);
}

int main(){
   pe_107();
   return 0;
}

srm470::div2::hard

グラフと見なすだけ。

#include <略>
using namespace std;

#define REP(i,a,n) for(int i=(a);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()

class ActivateGame{
public:
   int D(char c){
      return '0'<=c&&c<='9'?c-'0':'a'<=c&&c<='z'?c-'a'+10:c-'A'+36;
   }
   int findMaxScore(vector<string> grid){
      const int dx[] = {0,1,0,-1};
      const int dy[] = {1,0,-1,0};
      
      vector<pair<int,int> > vn;
      bool vcheck[50][50];
      rep(i,50)rep(j,50)vcheck[i][j]=false;
      vcheck[0][0]=true;
      vn.pb(mp(0,0));
      
      int ret = 0;
      for(;;){
         pair<int,int> next_id;
         int t_cost = -1;
         rep(i,vn.size()){
            rep(j,4){
               int tx = vn[i].first + dx[j];
               int ty = vn[i].second + dy[j];
               if( 0>tx || 0>ty || tx>=grid[0].size() ||
                     ty>=grid.size() || vcheck[ty][tx] ||
                     t_cost>abs(D(grid[vn[i].second][vn[i].first])-D(grid[ty][tx])) ) continue;
               
               t_cost = abs(D(grid[vn[i].second][vn[i].first])-D(grid[ty][tx]));
               next_id = pair<int,int>(tx,ty);
            }
         }
         if( t_cost == -1 ) break;
         vcheck[next_id.second][next_id.first] = true;
         vn.pb(next_id);
         ret += t_cost;
      }

      return ret;
   }
};

uva::11747

プリム法を愚直に組むと計算量がO(V^2)になり、TLEになる。
priority_queue使えば計算量はO(E logV)。無駄にバグで躓いた。

#include <略>
using namespace std;

#define REP(i,a,n) for(int i=(a);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()

int n,m;
int node[1000][1000];
int nncheck[1000][1000];

typedef pair<long long,pair<int,int> > pipii;

int main(){
   
   while(scanf("%d %d",&n,&m),n||m){
      rep(i,n)rep(j,n)node[i][j]=nncheck[i][j]=-1;
      rep(i,m){
         int a,b,c; scanf("%d %d %d",&a,&b,&c);
         node[a][b] = node[b][a] = c;
      }
      
      bool vcheck[1000];
      vector<int> ans;
      priority_queue<pipii,vector<pipii >, greater<pipii > > q;
      // pair<cost,(from,to)>
      rep(i,n)vcheck[i]=false;
      q.push(mp(999999999999LL,mp(0,0)));
      int now = 0;
      
      for(;;){
         rep(i,n)if( node[now][i]!=-1 && !vcheck[i] ){
            q.push( mp((long long)node[now][i],mp(now,i)) );
         }
         vcheck[now] = true;
         bool next = false;
         while( !q.empty() ){
            int from = q.top().second.first;
            now = q.top().second.second;
            q.pop();
            if( !vcheck[now] ){
               next = true;
               nncheck[from][now] = nncheck[now][from] = 1;
               break;
            }
         }
         if( next==false ){
            int i;
            for(i=0; i<n; i++)if( !vcheck[i] ){
               now = i;
               break;
            }
            if( i==n ) break;
         }
      }

      rep(i,n)REP(j,i+1,n)if( nncheck[i][j]==-1 && node[i][j]!=-1 ){
         ans.pb(node[i][j]);
      }
      
      if( ans.size()==0 ){
         puts("forest");
      }else{
         sort(all(ans));
         rep(i,ans.size()){
            if( i>0 )putchar(' ');
            printf("%d",ans[i]);
         }
         puts("");
      }
   }
   return 0;
}