首页 > 代码库 > luogu P1260 工程规划(luogu wa)don't know way
luogu P1260 工程规划(luogu wa)don't know way
题目描述
造一幢大楼是一项艰巨的工程,它是由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。
输入输出格式
输入格式:
第一行是用空格隔开的两个正整数n和m,下面的m行每行有三个用空格隔开的整数i,j,b对应着不等式Ti-Tj≤b。
输出格式:
如果有可行的方案,那么输出N行,每行都有一个非负整数且至少有一个为0,按顺序表示每个任务的起始时间。如果没有可行的方案,就输出信息“NO SOLUTION”。
输入输出样例
输入样例#1:
【样例输入1】5 81 2 01 5 –12 5 13 1 54 1 44 3 –15 3 –15 4 –3【样例输入2】5 51 2 –31 5 –12 5 –15 1 –54 1 4
输出样例#1:
【样例输出1】02541【样例输出2】NO SOLUTIO
差分约束
spfa
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m;struct node{ int next,v,w;}edge[5006];int head[1003];int num;void add_edge(int x,int y,int w){ edge[++num].next=head[x];edge[num].v=y;edge[num].w=w;head[x]=num;}int dis[1003];bool vis[1003];bool spfa(int x){ vis[x]=1; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].v; if(dis[v]>dis[x]+edge[i].w) { dis[v]=dis[x]+edge[i].w; if(!vis[v]) { if(!spfa(v)) return false; } else return false; } } vis[x]=0; return true;}int main(){ memset(dis,0x3f,sizeof dis); scanf("%d%d",&n,&m); int a,b,c; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); add_edge(b,a,c); } for(int i=1;i<=n;i++)add_edge(0,i,0); dis[0]=0; vis[0]=1; if(!spfa(0)) { puts("NO SOLUTION");return 0; } int minn=0x7fffffff; for(int i=1;i<=n;i++) { minn=min(minn,dis[i]); } for(int i=1;i<=n;i++) printf("%d\n",dis[i]-minn); return 0;}
luogu P1260 工程规划(luogu wa)don't know way
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。