계차 제약 소결 (poj 1201, poj 1716, poj 1364, poj 3159, poj 3169, poj 1275)

전체적인 느낌 에서 어 려 운 점 은 그림 을 만 드 는 것 이다. 그림 을 만 들 때 명확 하 게 제시 되 지 않 은 은밀 한 조건 을 고려 해 야 하기 때문이다. 모든 제약 관 계 를 다 찾 은 다음 에 최 단 로 (또는 최 장 로) 의 성격 을 정확하게 활용 해 야 정 답 을 얻 을 수 있다.
나의 수확 을 말 해 봐.
node 1: 구간 배치 요소 문제 에 대해 서 는 구간 개폐 성에 주의해 야 합 니 다. 즉, 점 에 대한 제약 에 관심 을 가 져 야 합 니 다.특히 각 점 에 요소 개 수 를 배치 하 는 제한 에 주의 하 세 요. 여 기 는 보통 관 계 를 포함 한 고찰 점 입 니 다 (상세 한 것 은 다음 글 참조).
node 2: 차이 점 부등식, a - b < = c 에 대해 b 에서 a 의 가중치 가 c 의 변 을 만 들 고 가장 짧 은 길 을 구 하 며 최대 치 를 얻 었 습 니 다.부등식 a - b > = c, b 에서 a 까지 의 가중치 가 c 의 변 을 만 들 고 가장 긴 길 을 구 하 며 가장 작은 값 을 얻 었 습 니 다.네 거 티 브 링 이 존재 하면 풀 리 지 않 고 최 단 로 (dist [] 가 업데이트 되 지 않 았 다) 를 구하 지 못 하면 임의로 풀 수 있 습 니 다.
node 3: 그림 을 만 들 때 가끔 허점 을 사용 합 니 다. 이 점 에서 그림 에 있 는 모든 실제 점 의 거리 (dist []) 는 0 입 니 다. 물론 이 점 의 역할 은 그림 속 의 점 입 대 를 편리 하 게 하 는 것 입 니 다 (spfa 알고리즘). 그리고 이런 실제 점 의 dist [] 를 업데이트 할 가치 가 있 습 니 다. 사실은 가끔 우 리 는 이 점 을 생략 하고 수 동 으로 모든 실제 점 을 팀 에 가입 시 키 는 동시에 이런 실제 점 의 dist [] 를 업데이트 할 수 있 습 니 다.값 과 visit [] 값.
POJ 1201 / ZOJ 1508 / HDU 1384 Intervals (문제 풀이 보고서)
이 문 제 는 바로 정수 구간 문제 이다. 전형 적 인 차이 점 제약 문제 이다. 문 제 는 모든 점 에 원 소 를 넣 지 않 거나 원 소 를 넣 으 라 고 요구 했다. 그러면 우 리 는 이 요구 에 따라 변 을 넣 을 수 있다. 0 < = s [i + 1] - s [i] < = 1.이것 이 바로 위 에서 말 한 은밀 한 조건 의 응용 이다.
POJ1716 Integer Intervals
이 문 제 는 위 에 있 는 거세 판 으로 각 구간 의 점 의 크기 관 계 를 정 치 를 정 하고 다른 것 은 같다.

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#include<queue>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;

const int N = 10010;

struct Edge{
	int s,e,v,next;
}edge[3*N];

int m,e_num,left,right,head[N],vis[N],dist[N];

void AddEdge(int a,int b,int c){
	edge[e_num].s=a; edge[e_num].e=b; edge[e_num].v=c;
	edge[e_num].next=head[a]; head[a]=e_num++;
}

queue <int> q;

void getmap(){
	int i,a,b;
	e_num=0; left=INT_MAX; right=INT_MIN;
	memset(head,-1,sizeof(head));
	while(m--){
		scanf("%d%d",&a,&b);
		AddEdge(a,b+1,2);
		left=min(left,a);
		right=max(right,b);
	}
	for(i=left;i<=right;i++){
		AddEdge(i,i+1,0);
		AddEdge(i+1,i,-1);
	}
	for(i=left;i<=right;i++){
		q.push(i);
		vis[i]=1;
		dist[i]=0;
	}
}

void spfa(){
	int i;
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		vis[cur]=0;
		for(i=head[cur];i!=-1;i=edge[i].next){
			int u=edge[i].e;
			if(dist[u]-dist[cur]<edge[i].v){
				dist[u]=dist[cur]+edge[i].v;
				if(!vis[u]){
					q.push(u); vis[u]=1;
				}
			}
		}
	}
	printf("%d
",dist[right+1]);
}

int main()
{
	while(~scanf("%d",&m))
	{
		getmap();
		spfa();
	}
	return 0;
}

POJ1364/ZOJ1260 King (문제 풀이 보고서)
상세 한 것 은 문제 풀이 보고 서 를 보십시오.
POJ3159 Candies
이 문 제 는 그림 을 만 들 지 않 고 모든 구속 관 계 를 당신 에 게 주 었 습 니 다. 주어진 부등식 에 따라 변 을 만 들 면 됩 니 다. 하지만 spfa 를 사용 하면 대기 열 이 시간 을 초과 할 수 있 습 니 다.
데 이 터 를 내 는 것 같 아서 일부러 이렇게 놀 았 습 니 다. 스 택 으로 바 꾸 세 요. 스 택 과 팀 의 성격 차이 (한 개 후진 이 먼저 나 오고 한 개 는 먼저 나 갑 니 다) 로 인해 카드 대열 의 데 이 터 를 스 택 으로 바로 죽 일 수 있 습 니 다. 물론 반대로 도 마찬가지 입 니 다. 저 는 이 문 제 를 대기 열 spfa 를 사용 하기 시 작 했 습 니 다. 시간 이 초과 되 었 습 니 다. 대신 XH 의 지 시 를 듣 고 팀 을 스 택 으로 바 꾸 면 A 입 니 다. 효율 이 좋 습 니 다.물론 '정직한' ACMer 로 서 우 리 는 데이터 가 인자 하 다 고 가정 할 수 없 으 니 힙 을 사용 하 세 요. 가뭄 과 침수 에 도 불구 하고 수확 을 보장 합 니 다.
코드:

#include<cstdio>
#include<stack>
#include<climits>
#include<cstring>
using namespace std;
const int N = 30010;

struct Edge{
	int s,e,next,v;
}edge[5*N];

int e_num,dist[N],vis[N],head[N];

void AddEdge(int a,int b,int c){
	edge[e_num].s=a; edge[e_num].e=b; edge[e_num].v=c;
	edge[e_num].next=head[a]; head[a]=e_num++;
}

void spfa(int n){
	int i;
	stack <int>q;
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;dist[i++]=INT_MAX);
	
	q.push(1);vis[1]=1;
	dist[1]=0;

	while(!q.empty()){
		int cur=q.top();
		q.pop();
		vis[cur]=0;
		for(i=head[cur];i!=-1;i=edge[i].next){
			int u=edge[i].e;
			if(dist[u]-dist[cur]>edge[i].v){
				dist[u]=dist[cur]+edge[i].v;
				if(!vis[u]){
					q.push(u);
					vis[u]=1;
				}
			}
		}
	}
	printf("%d
",dist[n]);
}

int main()
{
	int n,m,a,b,c;
	scanf("%d%d",&n,&m);
	e_num=0;
	memset(head,-1,sizeof(head));
	while(m--){
		scanf("%d%d%d",&a,&b,&c);
		AddEdge(a,b,c);
	}
	spfa(n);
	return 0;
}

POJ3169 Layout
이 문 제 는 점 에 있 는 요소 의 갯 수 에 대해 특별히 설명 을 했 습 니 다. 여러 개의 요소 가 같은 점 에 있 을 수 있 기 때문에 가 변 을 넣 지 않 고 직접 그림 을 만들어 최 단 로 를 구하 면 됩 니 다.
코드:

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 1010;
struct Edge{
	int s,e,v,next;
}edge[20*N];

int n,ml,md,e_num,head[N],vis[N],dist[N],countx[N];

void AddEdge(int a,int b,int c){
	edge[e_num].s=a; edge[e_num].e=b; edge[e_num].v=c;
	edge[e_num].next=head[a]; head[a]=e_num++;
}

void getmap(){
	int i,a,b,c;
	e_num=0;
	memset(head,-1,sizeof(head));
	while(ml--){
		scanf("%d%d%d",&a,&b,&c);
		AddEdge(a,b,c);
	}
	while(md--){
		scanf("%d%d%d",&a,&b,&c);
		AddEdge(b,a,-c);
	}
	for(i=2;i<=n;i++)
		AddEdge(i,1,0);
}

void spfa(){
	int i;
	queue <int> q;

	memset(vis,0,sizeof(vis));
	memset(countx,0,sizeof(countx));
	for(i=1;i<=n;dist[i++]=INT_MAX);

	dist[1]=0; vis[1]=1; countx[1]++;
	q.push(1);

	int tmp=0;
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		vis[cur]=0;
		if(countx[cur]>n){
			tmp=-1;break;
		}
		for(i=head[cur];i!=-1;i=edge[i].next){
			int u=edge[i].e;
			if(dist[u]-dist[cur]>edge[i].v){
				dist[u]=dist[cur]+edge[i].v;
				if(!vis[u]){
					q.push(u); vis[u]=1;
					countx[u]++;
				}
			}
		}
	}
	if(tmp==-1)printf("%d
",tmp);
	else printf("%d
",dist[n]<INT_MAX?dist[n]:-2);
}

int main()
{
	scanf("%d%d%d",&n,&ml,&md);
	getmap();
	spfa();
	return 0;
}

POJ1275/ ZOJ1420/ HDU1529 Cashier Employment
검 은 책의 예 제 는 오래된 경전 이 고 어 려 웠 다. 나 는 오랫동안 고민 하고 나 서 야 나 왔 다.
이 문 제 는 그림 을 만 드 는 데 어려움 이 있 습 니 다. 보통 모든 제약 조건 을 생각 하기 쉽 지 않 습 니 다. 검 은 책 을 보고 설명 을 한 다음 에 보고 서 를 찾 아서 만 들 었 습 니 다. 그래서 제 못 생 긴 코드 를 붙 이지 않 고 문제 풀이 보고 서 를 보 여 주 는 것 이 좋 습 니 다.
감사:
http://hi.baidu.com/accplaystation/blog/item/7c6d10136ef28b856438db6b.html
http://happylch21.blog.163.com/blog/static/165639759201163084924988/