最小全域木の問題をすこし解いた
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; }