글 읽기 - 런타임 에러 왜뜨는걸까요 ㅠㅠ...

wyldecat 8년 전 0

플로우인건 알고있어서..! i+j 가 홀수인애들이랑 짝수인애들로 나누고..

source->짝수인애들 : 짝수애의 크기

짝수인애들->홀수인애들 : 무한

홀수인애들->sink : 홀수애의 크기

이렇게 설정하고 dinic 알고리즘을 구현하였는데요!!!!

런타임에러가 뜨네유... 제 환경에선 N=50,M=50정도 넣어봐도 무리없이 잘 나오는데 말입니다...

​

#include<stdio.h>
#include<vector>
#include<queue>
#include<cstdlib>

#define oo 2e9
using namespace std;

int N,M,ecnt;
struct edge{
    int v,c;
    edge* r;
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
edge e[100000];
vector<vector<edge*> > v;
vector<int> level;
vector<bool> visited;
void add_edge(int s,int a,int c)
{
    edge* aa=&e[ecnt++];
    edge* bb=&e[ecnt++];
    aa->v=a;
    aa->c=c;
    bb->v=s;
    bb->c=0;
    aa->r=bb;
    bb->r=aa;
    v[s].push_back(aa);
    v[a].push_back(bb);
}
int dfs(int p,int q,int f) // 보낼 수 있는 플로우의 양
{
    if(p==q) return f;
    for(int i=0;i<v[p].size();i++)
    {
        edge* x=v[p][i];
        if(x->c>0 && level[p]<level[x->v])
        {
            int d=dfs(x->v,q,min(x->c,f));
            if(d>0)
            {
                x->c-=d;
                x->r->c+=d;
                return d;
            }
        }
    }
    return 0;
}
bool bfs()
{
    level=vector<int>(N*M+2,-1);
    queue<int> q;
    q.push(0);
    level[0]=0;
    while(!q.empty())
    {
        int x;
        int t=q.front();
        q.pop();
        for(int i=0;i<v[t].size();i++)
        {
            x=v[t][i]->v;
            if(level[x]!=-1 || v[t][i]->c==0) continue;
            level[x]=level[t]+1;
            if(x==N*M+1) return true;
            q.push(x);
        }
    }
    return false;
}
int maximum()
{
    int answer=0;
    while(bfs())
    {
        visited=vector<bool>(N*M+2,-1);
        answer+=dfs(0,N*M+1,oo);
    }
    return answer;
}
int main( )
{
    
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&M);
        ecnt=0;

        v=vector<vector<edge*> >(2502,vector<edge*>());
        
        int s=0;
        
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                int x,xx,yy;
                scanf("%d",&x);
                s+=x;
                if((i+j)%2==0)
                {
                    add_edge(0,i*N+j+1,x);
                    for(int l=0;l<4;l++)
                    {
                        xx=i+dx[l];
                        yy=j+dy[l];
                        if(xx<0 || yy<0 || xx>=N || yy>=M) continue;
                        add_edge(i*N+j+1,xx*N+yy+1,oo);
                    }
                }
                else
                {
                    add_edge(i*N+j+1,N*M+1,x);
                }
            }
        }
        printf("%d\n",s-maximum());
    }
    return 0;
}

wyldecat 8년 전 0

바보인가봅니다.. i*N+j+1 로 넘버링을 해줘서 틀렸었네요..

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

문제

문제

출처

ICPC

런타임 에러 왜뜨는걸까요 ㅠㅠ...

wyldecat 8년 전 0

wyldecat 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말