글 읽기 - 조언을 부탁드립니다.

(追記) (追記ここまで)

조언을 부탁드립니다.

11111번 - 두부장수 장홍준 2

elvpfhhrm 3년 전 0

계속 OutOfBounds가 떠서 고쳐보려 이리 바꾸고 저리 바꾸다. 이런 코드가 되었습니다. 어디에서 잘못된 건지 저 스스로 파악이 되지 않습니다. 다 지워버리고 처음부터 다시 하려 하는데, 무엇이 문제였는지는 알고 싶어 고수님들의 조언을 부탁드립니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int INF=999999999;
const int MAX=2505;
struct Edge
{
 int to,cap,cost,flow;
 Edge* reverse;
 
 Edge(int _to,int _cap, int _cost,int _flow=0)
 :to(_to),cap(_cap),cost(_cost),flow(_flow){}
 
 int GetSpare()
 {
 return cap-flow;
 }
 
 void AddFlow(int flowAmount)
 {
 flow+=flowAmount;
 reverse->flow-=flowAmount;
 }
 
};
int N,M,src=0,sink=2501,V;
vector<vector<Edge*>> edges;//[MAX];
char map[51][51];
bool checkBoard[51][51];
int pos[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void AddEdge(int from,int to,int cap, int cost)
{
 Edge* edge1=new Edge(to,cap,cost);
 Edge* edge2=new Edge(from,0,-cost);
 edge1->reverse=edge2;
 edge2->reverse=edge1;
 edges[from].push_back(edge1);
 edges[to].push_back(edge2);
}
int GetCost(char fir,char sec)
{
 int cost;
 
 switch(fir)
 {
 case 'A':
 switch(sec)
 {
 case 'A':
 cost=10;
 break;
 case 'B':
 cost=8;
 break;
 case 'C':
 cost=7;
 break;
 case 'D':
 cost=5;
 break;
 case 'F':
 cost=1;
 break;
 }
 break;
 case 'B':
 switch(sec)
 {
 case 'A':
 cost=8;
 break;
 case 'B':
 cost=6;
 break;
 case 'C':
 cost=4;
 break;
 case 'D':
 cost=3;
 break;
 case 'F':
 cost=1;
 break;
 }
 break;
 case 'C':
 switch(sec)
 {
 case 'A':
 cost=7;
 break;
 case 'B':
 cost=4;
 break;
 case 'C':
 cost=3;
 break;
 case 'D':
 cost=2;
 break;
 case 'F':
 cost=1;
 break;
 }
 break;
 case 'D':
 switch(sec)
 {
 case 'A':
 cost=5;
 break;
 case 'B':
 cost=3;
 break;
 case 'C':
 cost=2;
 break;
 case 'D':
 cost=2;
 break;
 case 'F':
 cost=1;
 break;
 }
 break;
 case 'F':
 switch(sec)
 {
 case 'F':
 cost=0;
 break;
 default:
 cost=1;
 break;
 }
 break;
 }
 return -cost;
}
void MCMF()
{
 int MaxCost=0;
 while(true)
 {
 vector<Edge*> path(MAX);
 vector<int> parents(MAX,-1);
 vector<bool> InQueue(MAX);
 vector<int> nowCost(MAX,INF);
 queue<int> q;
 
 q.push(src);
 parents[src]=src;
 nowCost[src]=0;
 InQueue[src]=true;
 while(!q.empty())
 {
 int now=q.front();
 q.pop();
 InQueue[now]=false;
 for(Edge *e:edges[now])
 {
 int next=e->to;
 
 if(e->GetSpare()>0&&nowCost[next]>nowCost[now]+e->cost)
 {
 nowCost[next]=nowCost[now]+e->cost;
 parents[next]=now;
 path[next]=e;
 if(!InQueue[next])
 {
 q.push(next);
 InQueue[next]=true;
 }
 }
 }
 }
 
 if(parents[sink]==-1)
 break;
 
 int minFlow=INF;
 for(int p=sink;p!=src;p=parents[p])
 {
 minFlow=min(minFlow,path[p]->GetSpare());
 }
 for(int p=sink;p!=src;p=parents[p])
 {
 path[p]->AddFlow(minFlow);
 MaxCost+=path[p]->cost*minFlow;
 }
 }
 cout<<-MaxCost<<'\n';
}
int main()
{
 FAST
 cin>>N>>M;
 
 V=N*M+5;
 edges=vector<vector<Edge*>>(V);
 bool isBlack=true;
 for(int i=1;i<=N;i++)
 {
 if(i%2==1)
 isBlack=true;
 else
 isBlack=false;
 
 for(int j=1;j<=M;j++)
 {
 cin>>map[i][j];
 checkBoard[i][j]=isBlack;
 isBlack=!isBlack;
 }
 }
 
 for(int i=1;i<=N;i++)
 {
 for(int j=1;j<=M;j++)
 {
 if(checkBoard[i][j])
 {
 AddEdge(src,i*M+j,1,0);
 for(int k=0;k<4;k++)
 {
 int nextI=i+pos[k][0];
 int nextJ=j+pos[k][1];
 
 if(nextI<1||nextI>N||nextJ<1||nextJ>M)
 continue;
 
 AddEdge(i*M+j,nextI*M+nextJ,1,GetCost(map[i][j],map[nextI][nextJ]));
 }
 }
 
 AddEdge(i*M+j,sink,1,0);
 }
 }
 MCMF();
 
 return 0;
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

조언을 부탁드립니다.

elvpfhhrm 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말