結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー akakimidori
提出日時 2019-03-20 01:14:09
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,674 bytes
コンパイル時間 737 ms
コンパイル使用メモリ 32,128 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:23:01
合計ジャッジ時間 2,000 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0