M_sea

洛谷1260 工程规划
题目描述造一幢大楼是一项艰巨的工程,它是由n个子任务构成的,给它们分别编号1,2,…,n(5≤n≤1000)。由于...
扫描右侧二维码阅读全文
30
2018/07

洛谷1260 工程规划

题目描述

造一幢大楼是一项艰巨的工程,它是由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\leq b$,从节点$j$向节点$i$连一条边权为$b$的边。

然后建一个0节点,向其它节点连一条权值为0的边。

再从0开始SPFA,顺便判负环。

得到的$dis[]$即为一组可行解。

然后再处理一遍,得到满足题目要求的解。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define re register
using namespace std;

struct Edge { int v,w,nxt; };
Edge e[10010];
int head[1010],sume=0;

inline void addEdge(int u,int v,int w) {
    e[++sume].v=v; e[sume].w=w;
    e[sume].nxt=head[u]; head[u]=sume;
}

int n,m;

int dis[1010];
bool inq[1010];
int cnt[1010];
bool f=0;
queue<int> Q;

inline void SPFA(int s) {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=cnt[s]=0,inq[s]=1; Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if (cnt[v]>=n) { f=1; return; }
                if (!inq[v]) { Q.push(v); inq[v]=1; }
            }
        }
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for (re int i=1;i<=m;i++) {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        addEdge(y,x,z);
    }
    for (re int i=1;i<=n;i++) addEdge(0,i,0);
    SPFA(0);
    if (f) { printf("NO SOLUTION\n"); return 0; }
    int Min=2147483647;
    for (re int i=1;i<=n;i++)
        if (dis[i]<Min) Min=dis[i];
    int add=-Min;
    for (re int i=1;i<=n;i++) printf("%d\n",dis[i]+add);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 52 PM

发表评论