M_sea

洛谷1260 工程规划
Luogu算法显然是差分约束(入门题?)对于每个条件$T_i-T_j\leq b$,从节点$j$向节点$i$连一条...
扫描右侧二维码阅读全文
30
2018/07

洛谷1260 工程规划

Luogu

算法

显然是差分约束(入门题?)

对于每个条件$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 月 30 日 10 : 05 PM

发表评论