HDOJ 2647 Reward [역 토폴로지 정렬 + 레이 어 링]

제목: 모든 사람의 기본급 은 888 입 니 다. 일부 사람들 은 자신의 수준 이 비교적 높다 는 것 을 보 여 주 려 고 하기 때문에 다른 사람 중 한 사람 보다 월급 을 많이 받 아야 합 니 다. 그들의 요 구 를 만족 시 킬 수 있 느 냐 고 물 었 습 니 다. 할 수 있다 면 최종 적 으로 모두 얼 마 를 지불해 야 합 니까? 할 수 없다 면 수출 - 1.
정책: 토폴로지 정렬.
이 문 제 는 어 려 운 점 이 있 습 니 다. 첫째, 데이터 가 크 고 2 차원 배열 을 만 들 면 안 됩 니 다. 다른 데이터 구조 (vector, 또는 체인 식 전방 향 성 (본 문제 코드 는 체인 식 전방 향 성) 을 바 꿔 야 합 니 다.2. 역 토폴로지 정렬 (즉 + in [b] 을 + in [a] 로 바 꾸 는 것), 3 차원 (위의 돈 수 + 1 에 따라).
체인 이 무엇 인지 모 르 겠 습 니 다.http://blog.csdn.net/acdreamers/article/details/16902023
코드:

#include
#include
#include
#define MAXN 10005
int head[MAXN*2];
struct EdgeNode{
	int to;
	int next;
};
EdgeNode edges[MAXN*2];
int in[MAXN], queue[MAXN], money[MAXN];
int n, ans;
int toposort()
{
	ans = 0;
	memset(money, 0, sizeof(money));
	int i, j;
	int iq = 0;
	for(i = 1; i <= n; i ++){
		if(!in[i]){
			queue[iq++] = i;
		}
	}
	for( i = 0; i < iq; i ++){
		int temp = queue[i];
		ans += money[temp];
		for(j = head[temp]; j != -1; j = edges[j].next){
			if(!--in[edges[j].to]){
				queue[iq++] = edges[j].to;
				money[edges[j].to] = money[temp]+1;//      ，
			}
		}
	}
	return iq == n;
}
int main()
{
	int m, i, a, b;
	while(scanf("%d%d", &n, &m) == 2){
		memset(head, -1, sizeof(head));
		memset(in, 0, sizeof(in));
		for(i = 0; i < m; i ++){
			scanf("%d%d", &a, &b);
				in[a]++;
				edges[i].to = a;
				edges[i].next = head[b];
				head[b] = i;
		}
		int sum = 888*n;
		int flag = toposort();
		printf("%d
", flag?sum+ans:-1);
	}
	return 0;
}

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2647

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[APIO2009] 스윕 계획(강연통 컴포넌트+축소점+토폴로지 정렬+dp)

제목: 지정된 시작점에서 시작하여 임의의 지정된 끝점까지 멈추는 지향도를 지정하여 지나간 모든 결점의 최대 점권과포인트, 모서리 수<=500000 하나의 강연통분량 내의 점은 서로 도달할 수 있기 때문에 그 중의 한...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDOJ 2647 Reward [역 토폴로지 정렬 + 레이 어 링]

좋은 웹페이지 즐겨찾기