Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1989-87dc0559
この記事にトラックバックする(FC2ブログユーザー)

SRM506 DIV1 MEDIUM - SlimeXGrandSlimeAuto (この記事を編集する[管理者用])

Source

TopCoder SRM506 DIV1 MEDIUM (600pt)
Problem Statement
SRM506 DIV1 自分の参加記録

問題概要

ノード数N (50以下) で連結なグラフが与えられる.枝には距離が定義されている.
最初,ノード0にいて,順番に訪れたいノードが50個以下与えられる.
最初,車が50個以下あって,車の置いてあるノードが与えられる.
車に乗ると,どこまででも乗れるが,一度降りるとその車は消滅する.(訪れたいノードに訪れるときは降りなければ訪れたとみなされない)
歩行スピードと車スピードが与えられる.
目的地を順番に行くのにかかる最小時間を求める問題.
(距離や時間の計算は,オーバーフローの心配のないぐらいの整数演算で完結できる程度の範囲)

解法

まず,何処と何処の移動の間で,どの車を使うことで,どれだけの時間を省略できるかを全部求める.
後は,2部グラフの最大重みマッチングになるので,最小費用流などで解く.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

typedef struct struct_listgraphintcostintflow{
  int node, nodeMemory;
  int *edgeSize, *edgeMemory;
  int **edge, **cost, **flow, **reverse;
} ListGraphIntCostIntFlow;

ListGraphIntCostIntFlow NewListGraphIntCostIntFlow(int maxNode,int maxDegree){
  int i; ListGraphIntCostIntFlow res;
  res.node=0; res.nodeMemory=maxNode;
  res.edgeSize   = (int*)malloc(maxNode*sizeof(int));
  res.edgeMemory = (int*)malloc(maxNode*sizeof(int));
  res.edge = (int**)malloc(maxNode*sizeof(int*));
  res.cost = (int**)malloc(maxNode*sizeof(int*));
  res.flow = (int**)malloc(maxNode*sizeof(int*));
  res.reverse = (int**)malloc(maxNode*sizeof(int*));
  if(maxDegree){
    rep(i,maxNode) res.edge[i]=(int*)malloc(maxDegree*sizeof(int));
    rep(i,maxNode) res.cost[i]=(int*)malloc(maxDegree*sizeof(int));
    rep(i,maxNode) res.flow[i]=(int*)malloc(maxDegree*sizeof(int));
    rep(i,maxNode) res.reverse[i]=(int*)malloc(maxDegree*sizeof(int));
  }
  rep(i,maxNode) res.edgeMemory[i]=maxDegree;
  return res;
}

void DeleteListGraphIntCostIntFlow(ListGraphIntCostIntFlow g){
  int i;
  rep(i,g.nodeMemory) if(g.edgeMemory[i]){free(g.edge[i]); free(g.cost[i]); free(g.flow[i]); free(g.reverse[i]);}
  free(g.edgeSize); free(g.edgeMemory); free(g.edge); free(g.cost);
}

void ListGraphIntCostIntFlowSetEmpty(ListGraphIntCostIntFlow *g,int node){
  int i;
  g->node = node;
  rep(i,node) g->edgeSize[i]=0;
}

void ListGraphIntCostIntFlowOneEdgeReallocEasy(ListGraphIntCostIntFlow *g,int k,int size,int fg){
  if(fg==1 && g->edgeMemory[k]>=size) return;
  if(g->edgeMemory[k]==size) return;
  if(g->edgeMemory[k]){free(g->edge[k]); free(g->cost[k]); free(g->flow[k]); free(g->reverse[k]);}
  g->edgeMemory[k]=size;
  g->edge[k] = (int*)malloc(size*sizeof(int));
  g->cost[k] = (int*)malloc(size*sizeof(int));
  g->flow[k] = (int*)malloc(size*sizeof(int));
  g->reverse[k] = (int*)malloc(size*sizeof(int));
}

void ListGraphIntCostIntFlowAddEdge(ListGraphIntCostIntFlow *g,int node1,int node2,int cost,int flow){
  int s1,s2;
  s1=g->edgeSize[node1]++, s2=g->edgeSize[node2]++;
  g->edge[node1][s1]=node2; g->cost[node1][s1]= cost; g->flow[node1][s1]=flow; g->reverse[node1][s1]=s2;
  g->edge[node2][s2]=node1; g->cost[node2][s2]=-cost; g->flow[node2][s2]=0;    g->reverse[node2][s2]=s1;
}



void intHeapGoUp(int n,int hp[],int hpi[],int d[]){
  int k,m;
  if(!n) return;
  m=(n-1)/2;
  if(d[hp[m]]<=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoUp(m,hp,hpi,d);
}

void intHeapGoDown(int n,int hp[],int hpi[],int hp_size,int d[]){
  int k,m;
  m=2*n+1; if(m>=hp_size) return;
  if(hp_size>m+1 && d[hp[m]]>d[hp[m+1]]) m++;
  if(d[hp[m]]>=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoDown(m,hp,hpi,hp_size,d);
}

void intHeapInsert(int n,int hp[],int hpi[],int *hp_size,int d[]){
  hp[*hp_size]=n; hpi[n]=(*hp_size)++;
  intHeapGoUp((*hp_size)-1,hp,hpi,d);
}

int intHeapDelete(int hp[],int hpi[],int *hp_size,int d[]){
  int r=hp[0]; hpi[r]=-1;
  if( *hp_size==1 ){(*hp_size)--; return r;}
  hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
  intHeapGoDown(0,hp,hpi,*hp_size,d);
  return r;
}


void ListGraphIntCostIntFlowDijkstra(ListGraphIntCostIntFlow g,int st,int ed,int res_dist[],int res_back_node[],int res_back_edge[],void *WorkMemory){
  int i,j,k,n=g.node,hp_size=0; int c;
  int *hp, *hpi;

  hp  = (int*) WorkMemory; WorkMemory = (void*)( hp  + n );
  hpi = (int*) WorkMemory; WorkMemory = (void*)( hpi + n );

  rep(i,n) hpi[i]=-1, res_dist[i]=1000000000, res_back_node[i]=-1; res_dist[st]=0;
  intHeapInsert(st,hp,hpi,&hp_size,res_dist);
  while(hp_size){
    i = intHeapDelete(hp,hpi,&hp_size,res_dist);
    if(i==ed) break;
    rep(j,g.edgeSize[i]) if(g.flow[i][j]>0) {
      k=g.edge[i][j]; c=res_dist[i]+g.cost[i][j];
      if(res_dist[k] <= c) continue; res_dist[k]=c; res_back_node[k]=i; res_back_edge[k]=j;
      if(hpi[k]<0) intHeapInsert(k,hp,hpi,&hp_size,res_dist);
      else         intHeapGoUp(hpi[k],hp,hpi,res_dist);
    }
  }
}

void ListGraphIntCostIntFlowMinCostFlow(ListGraphIntCostIntFlow g,int st,int ed,int flowLimit,int *res_flow,int *res_cost,void *WorkMemory){
  int i,j,k,l,flow_max;
  int *dist, *back_node, *back_edge;

  dist = (int*) WorkMemory; WorkMemory = (void*) (dist + g.node);
  back_node = (int*) WorkMemory; WorkMemory = (void*) (back_node + g.node);
  back_edge = (int*) WorkMemory; WorkMemory = (void*) (back_edge + g.node);
  
  *res_flow = *res_cost = 0;
  for(;;){
    if(flowLimit==0) break;
    
    ListGraphIntCostIntFlowDijkstra(g,st,-1,dist,back_node,back_edge,WorkMemory);
    if(back_node[ed]==-1) break;
    if(dist[ed]>=0) break;
    
    flow_max = flowLimit;
    k=ed;
    while(back_node[k]!=-1){
      i=back_node[k]; j=back_edge[k];
      if(flow_max > g.flow[i][j]) flow_max = g.flow[i][j];
      k=i;
    }
    k=ed;
    while(back_node[k]!=-1){
      i=back_node[k]; j=back_edge[k]; l=g.reverse[i][j];
      g.flow[i][j] -= flow_max; g.flow[k][l] += flow_max;
      k=i;
    }
    *res_flow += flow_max; *res_cost += flow_max * dist[ed];
    flowLimit -= flow_max;
  }
}


#define INF 1000000000

class SlimeXGrandSlimeAuto {
public:
int travel(vector <int> cars, vector <int> nd, vector <string> roads, int Walk, int Drive) {
  int i,j,k,n,mov,cs;
  int edge[55][55];
  int go[55][55];
  int res = 0, normal, usa;
  ListGraphIntCostIntFlow g = NewListGraphIntCostIntFlow(120,320);
  void *mem = malloc(9000000);
  int st, ed, node;
  int flow, cost;

  n = roads.size();
  rep(i,n) rep(j,n){
    if(roads[i][j]=='.') edge[i][j]=INF;
    if('0'<=roads[i][j]&&roads[i][j]<='9') edge[i][j]=roads[i][j]-'0'+1;
    if('a'<=roads[i][j]&&roads[i][j]<='z') edge[i][j]=roads[i][j]-'a'+11;
    if('A'<=roads[i][j]&&roads[i][j]<='Z') edge[i][j]=roads[i][j]-'A'+37;
  }
  rep(i,n) edge[i][i] = 0;

  rep(k,n) rep(i,n) rep(j,n) if(edge[i][j]>edge[i][k]+edge[k][j]) edge[i][j]=edge[i][k]+edge[k][j];

  nd.push_back(0);
  for(i=nd.size()-1;i;i--) nd[i]=nd[i-1];
  nd[0] = 0;
  
  mov = nd.size() - 1;
  cs = cars.size();

  rep(i,mov){
    normal = edge[nd[i]][nd[i+1]] * Walk;
    res += normal;
    rep(j,cs){
      usa = edge[nd[i]][cars[j]] * Walk + edge[cars[j]][nd[i+1]] * Drive;
      go[i][j] = normal - usa;
    }
  }

  node = mov + cs;
  st = node++; ed = node++;
  ListGraphIntCostIntFlowSetEmpty(&g,node);

  rep(i,mov) ListGraphIntCostIntFlowAddEdge(&g,st,i,0,1);
  rep(i,cs)  ListGraphIntCostIntFlowAddEdge(&g,mov+i,ed,0,1);
  rep(i,mov) rep(j,cs) ListGraphIntCostIntFlowAddEdge(&g,i,mov+j,-go[i][j],1);

  ListGraphIntCostIntFlowMinCostFlow(g,st,ed,INF,&flow,&cost,mem);
  res += cost;

  free(mem);
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1989-87dc0559
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。