글 읽기 - 2463번 비용입니다. 왜 Segmetation error가 나는지 모르겠어요

wwiiiii 9년 전 0

간선이 하나도 없는 상태에서 가장 큰것부터 하나씩 추가하며 역추적하는 방식을 사용했는데, 50%까지 채점하다가 Segmentation Fault가 나옵니다 ㅠ

graph는 그래프의 집합인데, 그래프는 그냥 그래프안에 있는 노드의 번호를 벡터에 넣어둔 것으로 구현했습니다.

graphindex는 노드가 어느 그래프에 속해있는지 그 그래프의 인덱스를 알려주는 그냥 배열입니다.

에러가 날 곳이 없는데 어디서 터지는지 못찾겠어요;

#include <cstdio>
#include <algorithm>
#include <vector>
#define BIG 1000000000

using namespace std;

int n, m, lastgraphindex;
long long int sumCost, pastCost;
long long int ans;
int graphindex[100010];///graphindex[j]는 번호가 j인 노드가 속한 그래프의 인덱스

class edge
{
	public:
		int u, v, cost;
		bool operator > ( const edge & ed) const
		 { 
				 if( cost > ed.cost) return true;
				 else if(cost == ed.cost) return u>ed.u;
				 return false;
		 }
		bool operator < ( const edge & ed) const
		 { 
				 if( cost < ed.cost) return true;
				 else if(cost == ed.cost) return u<ed.u;
				 return false;
		 }

};

vector<edge> container;
vector<int> graph[100010];

void ini()
{
	fill(&graphindex[0],&graphindex[100010],-1);
}

void input()
{
	edge temp;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&temp.u,&temp.v,&temp.cost);
		sumCost+=temp.cost;
		container.push_back(temp);
	}
}

void process()
{
    edge now;
	vector<edge>::iterator it=container.end();
	sort(container.begin(),container.end());
	while(true)
	{
		it--;
		now = *it;
		if(graphindex[now.u]==-1 && graphindex[now.v]==-1)//둘 다 그래프에 속하지 않은 경우
		{
			graphindex[now.u] = graphindex[now.v] = lastgraphindex;
			graph[lastgraphindex].push_back(now.u);
			graph[lastgraphindex].push_back(now.v);
			ans+= (sumCost - pastCost);
			lastgraphindex++;
			pastCost+=now.cost;
		}
		else if(graphindex[now.u]!=graphindex[now.v])//둘 중 최소한 하나가 그래프에 속했을 경우
		{
			if(graphindex[now.u]==-1 || graphindex[now.v]==-1)//둘 중 하나가 독립노드, 하나는 그래프에 속했을 경우
			{
				if(graphindex[now.u]==-1)//u가 그래프에 속한 노드 번호가 되게 한다
				{
					int temp=now.u;
					now.u=now.v, now.v= temp;
				}
				ans += graph[graphindex[now.u]].size() * (sumCost - pastCost);
				graphindex[now.v] = graphindex[now.u];
				graph[graphindex[now.u]].push_back(now.v);
				pastCost+=now.cost;
			}
			else//둘이 서로 다른 그래프에 속한 경우
			{
				ans +=  graph[graphindex[now.v]].size() * graph[graphindex[now.u]].size() * (sumCost - pastCost);
				int newindex = min(graphindex[now.v],graphindex[now.u]);
				if(newindex!=graphindex[now.v])
				{
					vector<int>::iterator it2;
					int tempindex = graphindex[now.v];
					for(it2 = graph[tempindex].begin(); it2!=graph[tempindex].end();++it2)
					{
						graph[newindex].push_back(*it2);
						graphindex[*it2]=newindex;
					}
				}
				else
				{
					vector<int>::iterator it3;
					int tempindex = graphindex[now.u];
					for(it3 = graph[tempindex].begin(); it3!=graph[tempindex].end();++it3)
					{
						graph[newindex].push_back(*it3);
						graphindex[*it3]=newindex;
					}
				}

				pastCost+=now.cost;			
			}
		}
		else//둘이 같은 그래프에 속한 경우
		{
			pastCost+=now.cost;
		}
		if(ans>=BIG) ans%=BIG;
		if(it==container.begin()) break;
	}
}

int main()
{
	input();
	ini();
	process();
	printf("%lld",ans%BIG);

}

baekjoon 9년 전 0

이 문제의 데이터는 직접 만든 것이 아니고, 공식 데이터를 사용하고 있습니다.

데이터에 문제의 조건에 맞지 않는 데이터가 하나 있습니다 (M = 0)

이 데이터를 삭제하고 다시 채점 하겠습니다.

baekjoon 9년 전 1

https://www.acmicpc.net/rejudge/status/116

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

문제

문제

출처

ICPC

2463번 비용입니다. 왜 Segmetation error가 나는지 모르겠어요

wwiiiii 9년 전 0

baekjoon 9년 전 0

baekjoon 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말