HackerRank Weekly Challenges - Week 2 5問目 - Road Network

Source

HackerRank Weekly Challenges - Week 2 5問目
problem statement（コンテストページ）
problem statement

問題概要

ノード数 $N$，枝数 $M$ の無向グラフが与えられる．
このグラフの枝はランダムに $2$ ノードを選んで作られていて，同じ節点間に複数の枝があったり，自分自身をつなぐ枝もあり得る．
枝 $k$ にはコスト $C_k$ が与えられ，これもランダムに選ばれている．
頂点 $i$ と $j$ が連結でなくなるように枝を削除することを考える．
ここで，削除する枝のコストの和の最小値を $w_{ij}$ とする．
全てのノード間の $w_{ij}$ の積
　　$\displaystyle \prod_{1 \leq i < j \leq N} w_{ij}$
を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．

解法

全ての接点間の最小カット $=$ 最大流を求めれば良い．
無向グラフの全接点間の最大流を求めるGomory-HuアルゴリズムでGomory-Hu treeを用いれば良い．
これは，$N$ 回の最大流を流せば求めることができる．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define ll long long
#define MD 1000000007

#define INT_INF 1000000000
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))

#define INT_LIST_MAX_FLOW_NODE 602
int intLmfEdge[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfFlow[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfInv[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfEdgeSize[INT_LIST_MAX_FLOW_NODE],intLmfEdgeMemory[INT_LIST_MAX_FLOW_NODE];
int intLmfLevel[INT_LIST_MAX_FLOW_NODE];

void intListMaxFlowLevelize(int n,int st,int ed){
  int i,j,k,t;
  int q[INT_LIST_MAX_FLOW_NODE],q_st,q_size;
  rep(i,n) intLmfLevel[i]=-1; intLmfLevel[st]=0; q_st=0; q_size=1; q[0]=st;
  while(q_size){
    i=q[q_st++]; q_size--; t=intLmfLevel[i]+1;
    rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
      k=intLmfEdge[i][j]; if(intLmfLevel[k]!=-1) continue;
      intLmfLevel[k]=t; q[q_st+q_size++]=k; if(k==ed) return;
    }
  }
}

int intListMaxFlowFlow(int i,int ed,int lim){
  int j,k,ret=0,t,s,ji;
  if(i==ed) return lim;
  rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
    k=intLmfEdge[i][j]; if(intLmfLevel[k]<=intLmfLevel[i]) continue;
    s=lim; if(s>intLmfFlow[i][j]) s=intLmfFlow[i][j];
    t=intListMaxFlowFlow(k,ed,s); if(!t) continue;
    ret+=t; lim-=t; ji=intLmfInv[i][j];
    intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t;
    if(!lim) break;
  }
  return ret;
}

int intListMaxFlow(int n,int st,int ed){
  int ret=0;
  for(;;){
    intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break;
    ret += intListMaxFlowFlow(st,ed,INT_INF);
  }
  return ret;
}

void intListMaxFlowEdgeInit(){
  int i;
  rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeInitAdv(int n){
  int i;
  rep(i,n) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){
  int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++;
  intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1;
  intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2;
  intLmfInv[n1][s1]=s2;  intLmfInv[n2][s2]=s1;
}

void intListMaxFlowDfs(int node,int start,int res[]){
  int i,j,k;
  int st[INT_LIST_MAX_FLOW_NODE], st_size=0;

  rep(i,node) res[i]=0; res[start]=1; st[st_size++]=start;
  while(st_size){
    i=st[--st_size];
    rep(k,intLmfEdgeSize[i]) if(intLmfFlow[i][k]){
      j=intLmfEdge[i][k]; if(res[j]) continue;
      res[j]=1; st[st_size++]=j;
    }
  }
}



/* Gomory-Hu's Algorithm ? */
/* int edge[][]が各枝のFlow，対称性があるedge[i][j]=edge[j][i] */
/* int res[][]に任意の2点間のmax-flowを計算する */

int edge[600][600], res[600][600];

void intMaxflowAnyPairOfNode(int node,void *WorkMemory){
  int i,j,a,b,flow;
  int *p, *fst;

  p=(int*)WorkMemory; WorkMemory=(void*)(p+node);
  fst=(int*)WorkMemory;

  rep(i,node) p[i]=0;
  rep(i,node) rep(j,node) res[i][j]=INT_INF;

  REP(i,1,node){
    intListMaxFlowEdgeInitAdv(node);
    rep(a,node) REP(b,a+1,node) if(edge[a][b]) intListMaxFlowEdgeAdd(a,b,edge[a][b],edge[b][a]);
    flow = intListMaxFlow(node,i,p[i]);
    intListMaxFlowDfs(node,i,fst);
    REP(j,i+1,node) if(fst[j] && p[i]==p[j]) p[j]=i;
    res[i][p[i]]=res[p[i]][i]=flow;
    rep(j,i) res[i][j]=res[j][i]=MIN(flow,res[p[i]][j]);
  }
}

int main(){
  int i, j, k, M, N;
  ll ans;
  void *mem=malloc(100000000);

  reader(&N, &M);
  rep(i,N) rep(j,N) edge[i][j] = 0;
  while(M--){
    reader(&i,&j,&k);
    i--; j--;
    edge[i][j] += k;
    edge[j][i] += k;
  }
  intMaxflowAnyPairOfNode(N, mem);

  ans = 1;
  rep(i,N) REP(j,i+1,N) ans = (ans * res[i][j]) % MD;
  writer((int)ans, '\n');

  return 0;
}

Current time: 2024年04月19日07時57分18秒
Last modified: 2014年09月22日23時25分24秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w2
トップページに戻る

Logged in as: unknown user (not login)

ログイン：