글 읽기 - 70퍼쯤에서 틀렸다고 뜨네요 ㅠㅠ

dtc03012 6년 전 0

제가 구현한 알고리즘은 일단 처음 주어진 배열로 scc를 만든다음

위상정렬을 하여

만약 a번째 scc에 최장 경로로 온 경로를 저장하여서 출력하게 했습니다.

왜냐하면 최장경로가 아닌 다른 경로로 왔을 경우에는 이게 위상정렬이므로 어떤 정점을 안 거치고 왔을 수 도 있기 때문입니다

혹시 반례가 있으면 가르쳐주십세요 ㅠㅠ

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#include <string>
#include <queue>
#include <vector>
using namespace std;
int n,m,curr,SN,sn[333],vis[333],fin[333],degree[333],go[333],parent[333],rr[333][333][2],out[333];
vector<vector<int> > scc;
vector<int> arr[333],sarr[333];
stack<int> s;
vector<pair<int,int> > inf,inf2;
int dfs(int n)
{
	vis[n]=++curr;
	s.push(n);
	int result=vis[n];
	for(int e=0;e<arr[n].size();e++)
	{
		int next=arr[n][e];
		if(vis[next]==0) result=min(result,dfs(next));
		else if(fin[next]==0) result=min(result,vis[next]);
	}
	if(result==vis[n])
	{
		vector<int> kk;
		while(1)
		{
			int now=s.top();s.pop();
			fin[now]=1;
			kk.push_back(now);
			sn[now]=SN;
			if(now==n) break;
		}
		SN++;
		scc.push_back(kk);
	}
	return result;
}
int main(void)
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		curr=0;
		SN=0;
		memset(sn,0,sizeof(sn));
		memset(vis,0,sizeof(vis));
		memset(fin,0,sizeof(fin));
		memset(go,-1,sizeof(go));
		memset(parent,-1,sizeof(parent));
		memset(degree,0,sizeof(degree));
		memset(rr,0,sizeof(rr));
		memset(out,0,sizeof(out));
		scc.clear();
		inf.clear();
		inf2.clear();
		for(int e=0;e<333;e++) arr[e].clear();
		for(int e=0;e<333;e++) sarr[e].clear();
		int n;
		scanf("%d",&n);
		string tmp;
		for(int e=1;e<=n;e++)
		{
			cin >> tmp;
			for(int p=0;p<n;p++)
			{
				if(e==p+1) continue;
				if(tmp[p]=='1') arr[e].push_back(p+1);
			}
		}
		for(int e=1;e<=n;e++) if(vis[e]==0) dfs(e);
		int tot=0;
		for(int e=0;e<SN;e++)
		{
			if(scc[e].size()==1) continue;
			for(int p=0;p<scc[e].size()-1;p++) inf2.push_back(make_pair(scc[e][p],scc[e][p+1]));
			inf2.push_back(make_pair(scc[e][scc[e].size()-1],scc[e][0]));
		}
		queue<int> q;
		for(int e=1;e<=n;e++)
		{
			for(int p=0;p<arr[e].size();p++)
			{
				int next=arr[e][p];
				if(sn[e]!=sn[next])
				{
					degree[sn[next]]++;
					out[sn[e]]++;
					sarr[sn[e]].push_back(sn[next]);
					rr[sn[e]][sn[next]][0]=e;
					rr[sn[e]][sn[next]][1]=next;
				}
			}
		}
		for(int e=0;e<SN;e++) if(degree[e]==0) 
		{
			go[e]=0;
			q.push(e);
		}
		while(!q.empty())
		{
			int now=q.front();q.pop();
			for(int e=0;e<sarr[now].size();e++)
			{
				int next=sarr[now][e];
				if(go[next]<go[now]+1)
				{
					parent[next]=now;
					go[next]=go[now]+1;
				}
				degree[next]--;
				if(degree[next]==0) q.push(next);
			}
		}
		for(int e=0;e<SN;e++)
		{
			if(out[e]==0)
			{
				int ee=e;
				while(parent[ee]!=-1)
				{
					inf.push_back(make_pair(parent[ee],ee));
					ee=parent[ee];
				}
			}
		} 
		cout << inf.size()+inf2.size() << "\n";
		for(int e=0;e<inf.size();e++) cout << rr[inf[e].first][inf[e].second][0] << " " << rr[inf[e].first][inf[e].second][1] << "\n";
		for(int e=0;e<inf2.size();e++) cout << inf2[e].first << " " << inf2[e].second <<"\n";
		cout << "\n";
	}
}

ehddml3 6년 전 1

저도 지금 풀고 있는데 같은 이유로 이런 케이스가 안되네요

3
101
011
001

dtc03012 6년 전 0

아오 ㅠㅠ 진짜 도저히 모르겠네요 ㅠㅠ 혹시나 푸시면 힌트라도 좀 알려주시면 감사하겠습니다..

dtc03012 6년 전 0

원래 scc로 돌리는걸 못하겠어요..

upple1 4년 전 0

아직 못 푸신 것 같아서 답글 남겨드립니다.

이 문제같은 경우 a->b->c로 가는 길이 있다고 판단되면 a->c 길이 없어도 됨을 알 수 있습니다.

이는 어떤 특정 알고리즘의 접근법이랑 유사합니다.

jhjh9501 4년 전 0

제가 엄청 고생했는데.. 윗분 말씀에 보충을 해서 설명을 하려고 합니다.

일단 SCC 간의 최적 경로.. 그러니까 연결되는 최적경로를 찾는데 위상정렬을 쓰면 안되고 플로이드-와샬을 써야하네요.

그 외의 최적경로를 찾는 알고리즘.. 경로값이 모두 양수니까 디엑스트라자 써도 괜찮을것같아요 제 생각에는.

위상정렬을 써서 찾는데 여러가지 방법이 있 겠지만..

제가 몇가지 시도 하다 마지막에 시도했던 방법은.. indegree가 0인 node들을 q에 넣고 돌리면서.

q 에 있는 애들의 next를 방문하면서 이 next들의 indegree들을 1씩 줄이고,

indegree가 0인된애들에 대해서 현재 - next 사이의 연결 경로를 만들어 주자. .이런거였는데,,,

결론적으로 말하면 연결 경로가 2개가 필요한 애들이 있어서 이러한 방법으로..하면 안되네요

얘를 들어서, 1, 2, 3, 4 node에 대해서

1>2, 2>4, 3>4 라고 합시다.. 위상정렬 결과는 1,2,3,4이고요

위 알고리즘대로 하면 3>4 만 연결을 하겠지만 사실은 2>4, 3>4 연결이 두개다 있어야 합니다.

그럼 그냥 위상정렬되어있는 애들을 순서대로 방문하는건 안되냐? 그러면 무조건 모든 SCC들이 더 연결되도록 방문할수있으니

조건에 위배되지 않잖아... 라고 할 수 있는데

문제가 두 개 있죠, 갈수없는 SCC 를 방문할 수 있겠죠 위 예시대로라면 2>3 은 방문하면 안되지만 위 방법대로 하면 방문하게됩니다.

위 문제만 해도 물론 방문할 수 없지만,

또 다른 문제는 최소 길을 방문할 수 없다는 점입니다.

1>3, 2>4 의 경우 위상정렬 결과가 1>2>3>4로 2개로 나타낼수있는데 위방법대로라면 4개가 필요하겠죠..

제가 고민한 내용을 정리할 겸 작성하였습니다.

도움이 되었으면 합니다.

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

문제

문제

출처

ICPC

70퍼쯤에서 틀렸다고 뜨네요 ㅠㅠ

dtc03012 6년 전 0

ehddml3 6년 전 1

dtc03012 6년 전 0

dtc03012 6년 전 0

upple1 4년 전 0

jhjh9501 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말