#326379 (C) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	akakimidori
提出日時	2019-03-20 01:14:09
言語	C (gcc 12.3.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	3,674 bytes
コンパイル時間	419 ms
コンパイル使用メモリ	32,068 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-24 14:57:45
合計ジャッジ時間	2,071 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	1 ms 4,348 KB
testcase_03	AC	1 ms 4,348 KB
testcase_04	AC	1 ms 4,348 KB
testcase_05	AC	1 ms 4,348 KB
testcase_06	AC	1 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	1 ms 4,348 KB
testcase_09	AC	1 ms 4,348 KB
testcase_10	AC	1 ms 4,348 KB
testcase_11	AC	1 ms 4,348 KB
testcase_12	AC	1 ms 4,348 KB
testcase_13	AC	1 ms 4,348 KB
testcase_14	AC	1 ms 4,348 KB
testcase_15	AC	1 ms 4,348 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	2 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	1 ms 4,348 KB
testcase_20	AC	1 ms 4,348 KB
testcase_21	AC	1 ms 4,348 KB
testcase_22	AC	1 ms 4,348 KB
testcase_23	AC	1 ms 4,348 KB
testcase_24	AC	1 ms 4,348 KB
testcase_25	AC	1 ms 4,348 KB
testcase_26	AC	1 ms 4,348 KB
testcase_27	AC	1 ms 4,348 KB
testcase_28	AC	1 ms 4,348 KB
testcase_29	AC	1 ms 4,348 KB
testcase_30	AC	1 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	1 ms 4,348 KB
testcase_34	AC	1 ms 4,348 KB
testcase_35	AC	1 ms 4,348 KB
testcase_36	AC	1 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB
testcase_38	AC	3 ms 4,348 KB
testcase_39	AC	1 ms 4,348 KB
testcase_40	AC	2 ms 4,348 KB
testcase_41	AC	1 ms 4,348 KB
testcase_42	AC	1 ms 4,348 KB
testcase_43	AC	1 ms 4,348 KB
testcase_44	AC	1 ms 4,348 KB
testcase_45	AC	1 ms 4,348 KB
testcase_46	AC	1 ms 4,348 KB
testcase_47	AC	2 ms 4,348 KB
testcase_48	AC	1 ms 4,348 KB
testcase_49	AC	1 ms 4,348 KB
testcase_50	AC	1 ms 4,348 KB
testcase_51	AC	2 ms 4,348 KB
testcase_52	AC	1 ms 4,348 KB
testcase_53	AC	2 ms 4,348 KB
testcase_54	AC	2 ms 4,348 KB
testcase_55	AC	1 ms 4,348 KB
testcase_56	AC	1 ms 4,348 KB
testcase_57	AC	1 ms 4,348 KB
testcase_58	AC	1 ms 4,348 KB
testcase_59	AC	2 ms 4,348 KB
testcase_60	AC	3 ms 4,348 KB
testcase_61	AC	2 ms 4,348 KB
testcase_62	AC	1 ms 4,348 KB
testcase_63	AC	1 ms 4,348 KB
testcase_64	AC	1 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int flow_type;

const flow_type flow_inf=10000;

typedef struct flow_edge{
  int vertex;
  int next;
  flow_type capacity;
} flow_edge;

typedef struct maxFlowGraph{
  flow_edge *edge;
  int *start;
  int vertex_num;
  int pointer;
  int edge_length;
} graph;

graph* newGraph(const int vertex_num){
  graph *g=(graph *)calloc(1,sizeof(graph));
  g->vertex_num=vertex_num;
  const int initial_length=4;
  g->edge=(flow_edge *)calloc(initial_length,sizeof(flow_edge));
  g->start=(int *)calloc(vertex_num,sizeof(int));
  g->pointer=0;
  g->edge_length=initial_length;
  for(int i=0;i<vertex_num;i++) g->start[i]=-1;
  return g;
}

void freeGraph(graph *g){
  free(g->edge);
  free(g->start);
  free(g);
}

void addEdge(graph *g,int from,int to,flow_type capa){
  if(g->pointer==g->edge_length){
    g->edge_length*=2;
    g->edge=(flow_edge *)realloc(g->edge,sizeof(flow_edge)*g->edge_length);
  }
  int p=g->pointer;
  g->edge[p]=(flow_edge){to,g->start[from],capa};
  g->start[from]=p;
  g->edge[p+1]=(flow_edge){from,g->start[to],0};
  g->start[to]=p+1;
  g->pointer+=2;
}

flow_type dinic_dfs(int v,graph *g,int dst,int *level,int *iter,flow_type e){
  if(v==dst) return e;
  flow_type sum=0;
  for(int p=iter[v];p!=-1 && e>0;p=g->edge[p].next,iter[v]=p){
    int u=g->edge[p].vertex;
    flow_type capa=g->edge[p].capacity;
    if(level[u]<=level[v] || capa<=0) continue;
    flow_type f=dinic_dfs(u,g,dst,level,iter,capa<e?capa:e);
    if(f>0){
      g->edge[p].capacity-=f;
      g->edge[p^1].capacity+=f;
      sum+=f;
      e-=f;
    }
  }
  return sum;
}

flow_type dinic(const graph *input_graph,const int src,const int dst){
  const int vertex_num=input_graph->vertex_num;
  const int edge_num=input_graph->pointer;
  graph *g=(graph *)calloc(1,sizeof(graph));
  g->edge=(flow_edge *)malloc(sizeof(flow_edge)*edge_num);
  g->start=(int *)malloc(sizeof(int)*vertex_num);
  memcpy(g->edge,input_graph->edge,sizeof(flow_edge)*edge_num);
  memcpy(g->start,input_graph->start,sizeof(int)*vertex_num);
  int *level=(int *)calloc(vertex_num,sizeof(int));
  int *queue=(int *)calloc(vertex_num,sizeof(int));
  int *iter=(int *)calloc(vertex_num,sizeof(int));
  flow_type flow=0;
  while(1){
    memset(level,0,sizeof(int)*vertex_num);
    int front=0,last=0;
    level[src]=1;
    queue[last++]=src;
    while(front<last && level[dst]==0){
      const int v=queue[front++];
      for(int p=g->start[v];p!=-1;p=g->edge[p].next){
	int u=g->edge[p].vertex;
	if(g->edge[p].capacity>0 && level[u]==0){
	  level[u]=level[v]+1;
	  queue[last++]=u;
	}
      }
    }
    if(level[dst]==0) break;
    memcpy(iter,g->start,sizeof(int)*vertex_num);
    while(1){
      flow_type f=dinic_dfs(src,g,dst,level,iter,flow_inf);
      if(f<=0) break;
      flow+=f;
    }
  }
  freeGraph(g);
  free(level);
  free(queue);
  free(iter);
  return flow;
}

#define MIN(a,b) ((a)<(b)?(a):(b))

void run(void){
  int n,m;
  scanf("%d%d",&n,&m);
  char *s=(char *)calloc(n*m+1,sizeof(char));
  int i,j;
  for(i=0;i<n;i++) scanf("%s",s+i*m);
  graph *g=newGraph(n*m+2);
  int w=0,b=0;
  int src=n*m;
  int dst=n*m+1;
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      if(s[i*m+j]=='.') continue;
      if((i+j)&1){
	b++;
	addEdge(g,i*m+j,dst,1);
	continue;
      }
      w++;
      addEdge(g,src,i*m+j,1);
      int d[]={-1,0,1,0};
      for(int k=0;k<4;k++){
	int x=i+d[k];
	int y=j+d[k^1];
	if(0<=x && x<n && 0<=y && y<m && s[x*m+y]!='.'){
	  addEdge(g,i*m+j,x*m+y,1);
	}
      }
    }
  }
  int c=dinic(g,src,dst);
  int d=MIN(w-c,b-c);
  int e=w+b-2*c-2*d;
  printf("%d\n",100*c+10*d+e);
}

int main(void){
  run();
  return 0;
}

yukicoder

結果

テストケース

ソースコード