結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2020-04-04 04:39:13 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 5,787 bytes |
コンパイル時間 | 2,670 ms |
コンパイル使用メモリ | 121,132 KB |
実行使用メモリ | 28,260 KB |
最終ジャッジ日時 | 2024-09-23 07:25:27 |
合計ジャッジ時間 | 4,760 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; static class Program{ const int mod=(int)1e9+7; static readonly int[][] di1=new int[][]{new int[]{-1,0},new int[]{1,0},new int[]{0,-1},new int[]{0,1}}; static readonly int[][] di2=new int[][]{new int[]{-1,-1},new int[]{-1,0},new int[]{-1,1},new int[]{0,-1},new int[]{0,1},new int[]{1,-1},new int[]{1,0},new int[]{1,1}}; static char[][] bm; static void Main(){ Sc sc=new Sc(); var s=sc.Ia; int h=s[0],w=s[1]; char c='.'; bm=new char[h+2][]; var qu=new Queue<Tuple<int,int,int>>(); for(int i = 1;i<=h;i++) {bm[i]=(c+sc.S+c).ToCharArray();} bm[0]=bm[h+1]=new string(c,w+2).ToCharArray(); var fl=new Mfp(h*w+10); int bc=0,wc=0; for(int i = 1;i<=h;i++) { for(int j = 1;j<=w;j++) { if(bm[i][j]=='b'){ fl.Edge(0,(i-1)*w+j+1,1); Fdi(i,j,(y,x)=>{ if(bm[y][x]=='w'){fl.Edge((i-1)*w+j+1,(y-1)*w+x+1,1);} }); bc++; } else if(bm[i][j]=='w'){fl.Edge((i-1)*w+j+1,1,1);wc++;} } } int p=fl.Dinic(0,1),z=Min(bc,wc)-p; Console.WriteLine("{0}",p*100+z*10+Abs(bc-wc)); } static void Fdi(int y,int x,Action<int,int> f){for(int i=0;i<4;i++){f(y+di1[i][0],x+di1[i][1]);}} } public class Mfp{ public List<int>[] li; private Dictionary<int,int>[] h; private bool[] b; private int[] l; private int n,ans,go; private const int inf=int.MaxValue; public Mfp(int n){ this.n=n; li=new List<int>[n]; h=new Dictionary<int,int>[n+1]; for(int i=0;i<n;i++){ li[i]=new List<int>(); h[i]=new Dictionary<int,int>(); } } public void Edge(int a,int b,int c){ if(a==b){return;} if(!h[a].ContainsKey(b)){ li[a].Add(b); li[b].Add(a); h[a].Add(b,c); h[b].Add(a,0); } else{h[a][b]+=c;} } public int Dinic(int st,int go){ this.go=st; ans=0; int z=1; while(z>0){ l=new int[n]; var qu=new Queue<Tuple<int,int>>(); qu.Enqueue(Tuple.Create(st,1)); l[st]=1; while(qu.Count>0){ var e=qu.Dequeue(); for(int i=0;i<li[e.Item1].Count;i++){ if(l[li[e.Item1][i]]==0&&h[e.Item1][li[e.Item1][i]]!=0){ l[li[e.Item1][i]]=e.Item2+1; qu.Enqueue(Tuple.Create(li[e.Item1][i],e.Item2+1)); } } if(e.Item1==go){break;} } b=new bool[n]; z=Fu3(go,inf); ans+=z; } return ans; } private int Fu3(int a,int p){ if(a==go){return p;} int u=0; for(int i=0;i<li[a].Count&&p>u;i++){ if(!b[li[a][i]]&&l[li[a][i]]<l[a]&&h[li[a][i]][a]!=0){ int z=Fu3(li[a][i],Min(p-u,h[li[a][i]][a])); h[li[a][i]][a]-=z; h[a][li[a][i]]+=z; u+=z; } } if(u==0){b[a]=true;} return u; } public int Ff(int st,int go){ this.go=go; ans=0; int z=1; while(z>0){ b=new bool[n]; z=Fu2(st,inf); ans+=z; } return ans; } private int Fu2(int a,int p){ if(a==go){return p;} int u=0; b[a]=true; for(int i=0;i<li[a].Count&&p>u;i++){ if(!b[li[a][i]]&&h[a][li[a][i]]!=0){ int z=Fu2(li[a][i],Min(p-u,h[a][li[a][i]])); h[a][li[a][i]]-=z; h[li[a][i]][a]+=z; u+=z; } } if(u!=0){b[a]=false;} return u; } public void Vc(int s,Action<int> f){ b=new bool[n]; Fu4(s,0,f); for(int i=0;i<li[s].Count;i++){ if(h[s][li[s][i]]==0&&!b[li[s][i]]){f(li[s][i]);} } } private void Fu4(int a,int p,Action<int> f){ b[a]=true; if((p&1)==0&&p!=0){f(a);} for(int i=0;i<li[a].Count;i++){ if(h[a][li[a][i]]!=0&&!b[li[a][i]]){Fu4(li[a][i],p+1,f);} } } } public class Sc{ public int I{get{return int.Parse(Console.ReadLine());}} public long L{get{return long.Parse(Console.ReadLine());}} public double D{get{return double.Parse(Console.ReadLine());}} public string S{get{return Console.ReadLine();}} public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}} public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}} public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}} public string[] Sa{get{return Console.ReadLine().Split();}} public object[] Oa{get{return Console.ReadLine().Split();}} public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}} public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);} public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);} public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}} public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);} public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);} public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}} public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);} public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);} public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;} public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;} public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;} public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;} }