POJ 1752 差分约束+输出路径

17-02-13 来源：[db:作者]

收藏我要投稿

POJ 1752 差分约束+输出路径：1.等式如 A - B = C。可以转化为 A - B >= C 和 A - B <= C两个不等式来等价，然后建边。

2. 输出路径：

可以通过判断 dis[i] - dis[i-1] == 1? 如成立则说明 i 是那个发生变化的点，即需要输出的节点。

3.最长路和最短路的区别：这道题是spj ，如果按最长路来做，则结果与样例相同，但按最短路来做结果是不一样的。两种做法都是正确的，区别在于在满足充分利用重叠区域空间（贪心的思想）的前提下，最长路是从右区间开始选点，而最短路是从左区间开始选点。

代码：

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include
#include
#include
using namespace std;
typedef long long ll;

const int INF = 1e8;
const int maxv = 20000 + 1;
const int maxn = 10010 * 4;
struct P{
	int v,w;
	int next;
}G[maxn*20];
int head[maxn],vis[maxn],dis[maxn],out[maxn];
int n,tot;

void init(void){
	tot = 0;
	memset(head,-1,sizeof(head));
}

void add(int u,int v,int w){
	G[tot].v = v;
	G[tot].w = w;
	G[tot].next = head[u];
	head[u] = tot++; 
}

void spfa(int st,int ed){
	queue que;
	for(int i=st ;i<=ed ;i++){
		vis[i] = 0;
		dis[i] = -INF;
	}
	dis[st] = 0;
	que.push(st);
	while(que.size()){
		int u = que.front();
		que.pop();
		vis[u] = 0;
		for(int i=head[u] ; i != -1 ; i=G[i].next){
			int v = G[i].v,w = G[i].w;
			if(dis[u] + w > dis[v]){
				dis[v] = dis[u] + w;
				if(!vis[v]){
					vis[v] = 1;
					que.push(v);
				}
			}
		}	
	}
}

void solve(int st,int ed){
	spfa(st,ed);
	printf("%d\n",dis[ed]);
	for(int i=st ;i<=ed ;i++){
		if(dis[i] - dis[i-1] == 1){
			printf("%d\n",i-maxv);
		}
	}
}

int main(){
	int k,m;
	while(scanf("%d%d",&k,&m) != EOF){
		init();
		int Min = INF,Max = 0;
		while(m--){
			int a,b;
			scanf("%d%d",&a,&b);
			if(a>b)	swap(a,b);
			int u = a + maxv - 1;
			int v = b + maxv;
			int w = v - u;
			Max = max(Max,v);
			Min = min(Min,u);
			if(w < k){
				add(u,v,w);
				add(v,u,-w);
			}
			else{
				add(u,v,k);
			}
		}
		for(int i=Min ;i<=Max ;i++){
			add(i,i+1,0);
			add(i+1,i,-1);
		}
		solve(Min,Max);
	}
	return 0;
}

点击复制链接与好友分享!回本站首页