首页 > 代码库 > UVALive 4885 Task 差分约束
UVALive 4885 Task 差分约束
题目链接:点击打开链接
题意:
有n个任务 m个限制条件
1、task i starts at least A minutes later than task j
表示 i - j >= A
2、task i starts within A minutes of the starting time of task j
表示 i - j <= A
问:每个任务开始的时间。 求一个任意解
思路:
差分约束,对于不等式形如:
点u,v : 常数C
有: u - v <= C
则从v->u 连一条长度为C的边。
若有负环则差分约束无解。否则就能求得一个任意解。
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> #include <string.h> using namespace std; #define inf 100000000 #define N 200 #define M 200005 struct node{ int from, to, dis, nex; }edge[M]; int head[N], edgenum; void init(){memset(head, -1, sizeof head); edgenum = 0;} void add(int u, int v, int d){ node E = {u, v, d, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int n, m; int dis[N], inq[N], tim[N]; bool spfa(){ memset(tim, 0, sizeof tim); memset(inq, 0, sizeof inq); dis[0] = 0; for(int i = 1; i <= n; i++) { dis[i] = inf; add(0, i, 0); } queue<int>q; q.push(0); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].to; if(dis[v] > dis[u] + edge[i].dis) { dis[v] = dis[u] + edge[i].dis; if(!inq[v]) { inq[v] = 1; tim[v]++; q.push(v); if(tim[v]>n)return false; } } } } return true; } char s[100]; void eat(int x){while(x--)scanf("%s",s);} void build(){ scanf("%d", &m); init(); int a, b, x, i; while(m--) { eat(1); scanf("%d", &a); eat(2); if(s[0] == 'a') { eat(1); scanf("%d", &x); eat(4); scanf("%d", &b); add(a, b, -x); } else { scanf("%d", &x); eat(7); scanf("%d", &b); add(b, a, x); } add(a, b, 0); } } void solve(){ build(); if(spfa() == false) { puts("Impossible."); return ;} int minn = dis[1]; for(int i = 2; i <= n; i++) minn = min(minn, dis[i]); minn = -minn +1; for(int i = 1; i <= n; i++) printf("%d%c", dis[i]+minn, i==n?'\n':' '); } int main() { int a, b, x, i; while(scanf("%d", &n), n){ solve(); } return 0; } /* 2 2 task 1 starts at least 5 minutes later than task 2 task 1 starts within 5 minutes of the starting time of task 2 2 2 task 1 starts at least 6 minutes later than task 2 task 1 starts within 5 minutes of the starting time of task 2 2 2 task 1 starts at least 5 minutes later than task 2 task 1 starts within 6 minutes of the starting time of task 2 2 2 task 2 starts at least 5 minutes later than task 1 task 1 starts within 5 minutes of the starting time of task 2 2 2 task 2 starts at least 0 minutes later than task 1 task 1 starts within 0 minutes of the starting time of task 2 ans: */
UVALive 4885 Task 差分约束
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。