保存されている過去のバージョンの一覧

2014年05月03日18時58分52秒

Codeforces Round #244 DIV2 C問題 - Checkposts

Source

Codeforces Round #244 DIV2 C問題 (1500pt)
Problem description

問題概要

ノード数 $N$,枝数 $M$ の有向グラフが与えられる.
自己ループはなく,始点も終点も同じという枝が $2$ つ以上あることはない.
また,各ノード $k$ に交番を作るためのコスト $C_k$ が与えられる.
ノード $i$ に交番を作ると,ノード $i$ と,ノード $i$ から辿りつけて,さらにノード $i$ に戻ってこれるようなノードが全て守られる.
全てのノードを守るために,最小コストで,その中で,最小個数の交番を作りたい.
最小コスト(${\rm mod}$ は取らない)と,そのような交番の建て方のパターン数を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

解法

強連結成分分解して,それぞれの成分について,最もコストの小さいノード $1$ つに建てれば良い.
建て方のパターン数は,それぞれの成分の最もコストの小さいノードの数の積.
コストが大きいのでオーバーフローに注意.

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 ll long long

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

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 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);}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];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);}

typedef struct struct_kdyenbxjdhd{
  int node, nodeMemory;
  int *edgeSize, *edgeMemory;
  int **edge;
}ListGraph;

ListGraph NewListGraph(int maxNode,int maxDegree){
  int i; ListGraph 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*));
  rep(i,maxNode) res.edgeMemory[i]=maxDegree;
  if(maxDegree) rep(i,maxNode) res.edge[i]=(int*)malloc(maxDegree*sizeof(int));
  return res;
}

void DeleteListGraph(ListGraph g){
  int i;
  rep(i,g.nodeMemory) if(g.edgeMemory[i]) free(g.edge[i]);
  free(g.edgeSize); free(g.edgeMemory); free(g.edge);
}

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

void ListGraphAddEdge(ListGraph *g,int node1,int node2){
  int s=g->edgeSize[node1]++;
  g->edge[node1][s]=node2;
}

void ListGraphAddBidirectedEdge(ListGraph *g,int node1,int node2){
  int s1,s2;
  if(node1==node2){
    s1=g->edgeSize[node1]++;
    g->edge[node1][s1]=node2;
  } else {
    s1=g->edgeSize[node1]++, s2=g->edgeSize[node2]++;
    g->edge[node1][s1]=node2; g->edge[node2][s2]=node1;
  }
}

/* edgeMemory[k]=sizeに変更する.中身のデータは破壊される. */
/* fg=1 ならば,すでにedgeMemory[k]>=sizeの場合は何もしない */
void ListGraphOneEdgeReallocEasy(ListGraph *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]);
  g->edgeMemory[k]=size;
  g->edge[k] = (int*)malloc(size*sizeof(int));
}

/* g.nodeは既に設定済み,edgeのメモリが足りてない場合は適当にメモリ確保するぜ */
void ListGraphSetDirectEdges(ListGraph *g,int from[],int to[],int size){
  int i,n=g->node;
  rep(i,n) g->edgeSize[i]=0;

  rep(i,size) g->edgeSize[from[i]]++;
  rep(i,n) {ListGraphOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
  rep(i,size) ListGraphAddEdge(g,from[i],to[i]);
}

void ListGraphSetBidirectEdges(ListGraph *g,int from[],int to[],int size){
  int i,n=g->node;
  rep(i,n) g->edgeSize[i]=0;

  rep(i,size) g->edgeSize[from[i]]++, g->edgeSize[to[i]]++;
  rep(i,n) {ListGraphOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
  rep(i,size) ListGraphAddBidirectedEdge(g,from[i],to[i]);
}

/* 番号つけるよ.stからDFSするよ.番号mxからつけるよ.最後につけた番号+1をreturnで返すよ. */
int ListGraphStronglyConnectedComponentsDFS(ListGraph *g,int num[],int st,int mx){
  int i,j,n=g->node;
  num[st]=-2;
  rep(i,g->edgeSize[st]) {
    j=g->edge[st][i]; if(num[j]==-1) mx=ListGraphStronglyConnectedComponentsDFS(g,num,j,mx);
  }
  num[st]=mx; return mx+1;
}

/* 強連結成分分解 */
/* gはグラフ,revはその逆グラフ(枝が向き逆) */
/* res[i]=res[j]ならばiとjは同類 */
/* return resの最大値+1 = 連結成分の数 */
int ListGraphStronglyConnectedComponents(ListGraph *g,ListGraph *rev,int res[],void *WorkMemory){
  int i,j,k,n=g->node,ret=0;
  int *st, st_size, *num, *nrv;

  st  = (int*) WorkMemory; WorkMemory = (void*)(st  + n);
  num = (int*) WorkMemory; WorkMemory = (void*)(num + n);
  nrv = (int*) WorkMemory;

  rep(i,n) res[i]=num[i]=-1; k=0;
  rep(i,n) if(num[i]==-1) k=ListGraphStronglyConnectedComponentsDFS(g,num,i,k);
  rep(i,n) nrv[num[i]]=i;

  for(k=n-1;k>=0;k--) {
    i=nrv[k]; if(res[i]>=0)continue;
    res[i]=ret; st_size=0; st[st_size++]=i;
    while(st_size){
      i=st[--st_size];
      rep(j,rev->edgeSize[i])
        if(res[rev->edge[i][j]]==-1) res[rev->edge[i][j]]=ret, st[st_size++]=rev->edge[i][j];
    }
    ret++;
  }

  return ret;
}

int N, M, u[400000], v[400000], c[200000];
int com[200000];
vector<int> cost[200000];

int main(){
  int i, j, k, x;
  ll res1, res2;
  ListGraph g = NewListGraph(110000, 0);
  ListGraph r = NewListGraph(110000, 0);
  void *mem = malloc(40000000);

  reader(&N);
  rep(i,N) reader(c+i);
  reader(&M);
  rep(i,M) reader(u+i), reader(v+i), u[i]--, v[i]--;

  g.node = r.node = N;
  ListGraphSetDirectEdges(&g, u, v, M);
  ListGraphSetDirectEdges(&r, v, u, M);

  res1 = 0; res2 = 1;
  x = ListGraphStronglyConnectedComponents(&g, &r, com, mem);

  rep(i,N) cost[com[i]].push_back(c[i]);
  rep(i,x){
    sort(cost[i].begin(), cost[i].end());
    res1 += cost[i][0];
    rep(j,cost[i].size()) if(cost[i][0] != cost[i][j]) break;
    res2 = res2 * j % 1000000007;
  }

  writer(res1, ' ');
  writer(res2, '\n');

  myed;
  return 0;
}

Current time: 2024年03月29日00時13分12秒
Last modified: 2014年05月03日18時58分52秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF244 CF_Div2_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: