2021.08.16 P1260 工程规划（差分约束）

重点：

1.跑最短路是为了满足更多约束条件。

P1260 工程规划 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

造一幢大楼是一项艰巨的工程，它是由n个子任务构成的，给它们分别编号1，2，…，n(5≤n≤1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1，T2，…，Tn并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。

这种要求就可以用M(5≤m≤5000)个不等式表示，不等式形如Ti-Tj≤b代表i和j的起始时间必须满足的条件。每个不等式的右边都是一个常数b，这些常数可能不相同，但是它们都在区间(-100，100)内。

你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列T1，T2，…，Tn，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T1，T2，…，Tn中至少有一个为0。

分析及代码：

//T_i-T_j<=b -> T_i<=T_j+b,咱来跑个最短路

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int N=1010;

const int inf=0x3f3f3f;

int n,m,cnt,head[N],vis[N],tot[N],dis[N];

struct node{

	int to,next,val;

}a[N<<1];

//呵呵了，题上标的m<=5000，我怎么没看到！第一次RE3个点，第二次改为5000依旧RE一个点，忽然想起来我加了超级源点，shitf！

struct nodei{

	int pos,dis;

	bool operator <(const nodei &b)const{

		return dis>b.dis;

	}

}; 

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void add(int u,int v,int w){

	++cnt;

	a[cnt].to=v;

	a[cnt].next=head[u];

	a[cnt].val=w;

	head[u]=cnt;

}

void spfa(int start){

	memset(dis,inf,sizeof(dis));

	priority_queue<nodei>q;

	dis[start]=0;

	vis[start]=tot[start]=1;

	q.push({start,0});

	while(!q.empty()){

		nodei tmp=q.top();q.pop();

		int x=tmp.pos;

		vis[x]=0;

		++tot[x];

		if(tot[x]>=n){

			cout<<"NO SOLUTION";

			return ;

		}

		for(int i=head[x];i;i=a[i].next){

			int v=a[i].to;

			if(dis[v]>dis[x]+a[i].val){

				dis[v]=dis[x]+a[i].val;

				if(!vis[v])q.push({v,dis[v]}),vis[v]=1;

			}

		}

	}

	int minn=inf;

	for(int i=1;i<=n;i++)minn=min(minn,dis[i]);

	for(int i=1;i<=n;i++)cout<<dis[i]-minn<<endl;

}

int main(){

	n=read();m=read();

	for(int i=1;i<=m;i++){

		int u,v,w;

		u=read();v=read();w=read();

		//cout<<u<<" "<<v<<" "<<w<<endl;//

		add(v,u,w);

	}

	for(int i=1;i<=n;i++)add(n+1,i,0);

	spfa(n+1);

	return 0;

}

巴特西

2021.08.16 P1260 工程规划（差分约束）

2021.08.16 P1260 工程规划（差分约束）

最新文章

热门文章