글 읽기 - 어디가 이상한지 모르겟어요

dfwdf77 6년 전 0

mcmf로 풀라고 했는데 어디서 잘못되었는지

찾지를 못하겠네요 ㅠㅠ

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 10000;
const int MAX_V = 2*MAX_N;
const int INF = 1000000000;

	int c[MAX_V][MAX_V];
	int d[MAX_V][MAX_V];
	int f[MAX_V][MAX_V];
		vector<int> adj[MAX_V];

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int qAA[6][6]={{10,8,7,5,0,1},
             {8,6,4,3,0,1},
             {7,4,3,2,0,1},
             {5,3,2,2,0,1},
             {0,0,0,0,0,0},
             {1,1,1,1,0,0}};
int N, M;
int conv[51][51];
char board[55][55];


int main(){

	scanf("%d %d", &N, &M);
	//fflush(stdin);
	for(int i=0;i<N;i++)
		{
			scanf("%s",board[i]);
		//	fflush(stdin);
	} 
	for(int i=0;i<N;i++)for(int j=0;j<M;j++)conv[i][j]=i*M+j;

	 int S = N*M, E = N*M+1;
		   for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if((i+j)&1){
                	c[N*M][conv[i][j]] = 1;
					c[conv[i][i]][N*M] = 0;
						d[conv[i][j]][N*M] = 0;
			d[N*M][conv[i][j]] = 0;
			adj[N*M].push_back(conv[i][j]);
			adj[conv[i][j]].push_back(N*M);
                for(int k=0;k<4;k++){
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(0<=nx && nx<N && 0<=ny && ny<M){
                        int x=qAA[board[i][j]-'A'][board[nx][ny]-'A'];
							c[conv[i][j]][conv[nx][ny]] = 1;
							c[conv[nx][ny]][conv[i][j]] = 0;
			d[conv[i][j]][conv[nx][ny]] = x;
			d[conv[nx][ny]][conv[i][j]] = -x;
			adj[conv[i][j]].push_back(conv[nx][ny]);
			adj[conv[nx][ny]].push_back(conv[i][j]);
                    }
                }
            }else{

					c[conv[i][j]][N*M+1] = 1;
					c[N*M+1][conv[i][j]] = 0;
						d[conv[i][j]][N*M*1] = 0;
			d[N*M+1][conv[i][j]] = 0;
			adj[conv[i][j]].push_back(N*M+1);
			adj[N*M+1].push_back(conv[i][j]);
            }
        }
    }
		   int final=N*M+2;
		int result = 0;
		while(1){
			int prev[MAX_V], dist[MAX_V];
			bool inQ[MAX_V];
			queue<int> Q;
			fill(inQ, inQ+MAX_V, false);
			fill(prev, prev+MAX_V, -1);
			fill(dist, dist+MAX_V, INF);
			dist[S] = 0;
			inQ[S] = true;
			Q.push(S);

			while(!Q.empty()){
				int curr = Q.front();
				Q.pop();
				inQ[curr] = false;
				for(int i=0;i<adj[curr].size();i++){
					int next=adj[curr][i];
					if(c[curr][next]-f[curr][next] > 0 && dist[next] > dist[curr] + d[curr][next]){
						dist[next] = dist[curr] + d[curr][next];
						prev[next] = curr;
						if(!inQ[next]){
							Q.push(next);
							inQ[next] = true;
						}
					}
				}
			}
			if(prev[E] == -1) break;
			int flow = INF;
			  for(int i=E; i!=S; i=prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);

			for(int i=E; i!=S; i=prev[i]){
				result += flow*d[prev[i]][i];
			   f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;

			}
		}
		printf("%d\n", result);
		scanf("%d",&N);
}

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

문제

문제

출처

ICPC

어디가 이상한지 모르겟어요

dfwdf77 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말