首页 > 代码库 > POJ 1201 Intervals 差分约束
POJ 1201 Intervals 差分约束
http://poj.org/problem?id=1201
TLE了很久,因为用了cin.....
思路和其他差分约束差不多,http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
如果区间[a, b]中至少有c个元素,如果用上面的博客,那么说明xa - xb >= c,但是注意这里是闭区间,xa - xb是不包括b这个点的,
就比如用了[a, b]有c个元素,[b, d]有x个,那么ans = c + x - 1个,因为有一个点是重合了的。
为了解决这个问题,重新定义,令xa - x(b+1) >= c代表区间[a, b]拥有的数量,其实这是显然的,只不过刚开始习惯用xa - xb代表[a, b]
没想到-xb是不包括b的。
这里还有一个问题就是区间不连续,所以跑不了最长路的问题。
[1, 4] >= 2 [6, 7] >= 2
无法跑spfa
所以要加边:
[3, 3]拥有的数量是 >= 0 <= 1的,
所以
x3 - x4 >= 0
x3 - x4 <= 1
的
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> #include <time.h> #include <iomanip> const int maxn = 2e5 + 20; struct Edge { int u, v, w, tonext; }e[maxn * 2]; int num, first[maxn]; void addEdge(int u, int v, int w) { ++num; e[num].u = u, e[num].v = v, e[num].w = w, e[num].tonext = first[u]; first[u] = num; } queue<int> que; int in[maxn], dis[maxn], tim[maxn]; bool spfa(int bx, int n) { //从bx开始,有n个顶点 for (int i = 1; i <= n; ++i) { dis[i] = inf; tim[i] = 0; //入队次数清0 in[i] = false; //当前这个节点不在队列里 } while (!que.empty()) que.pop(); que.push(bx), in[bx] = true, dis[bx] = 0, tim[bx]++; while (!que.empty()) { int u = que.front(); if (tim[u] > n) return true; //入队次数超过n次,出现负环 que.pop(); //in[u] = false ? for (int i = first[u]; i; i = e[i].tonext) { if (dis[e[i].v] > dis[e[i].u] + e[i].w) { dis[e[i].v] = dis[e[i].u] + e[i].w; if (!in[e[i].v]) { //不在队列 que.push(e[i].v); in[e[i].v] = true; tim[e[i].v]++; } } } in[u] = false; } return false; } void work() { // memset(first, -1, sizeof first); int n; cin >> n; int mx = 0; for (int i = 1; i <= n; ++i) { int u, v, w; cin >> u >> v >> w; // if (u > v) swap(u, v); ++u; ++v; ++v; mx = max(mx, v); addEdge(u, v, -w); } for (int i = 1; i < mx; ++i) { addEdge(i, i + 1, 0); addEdge(i + 1, i, 1); } spfa(1, mx); // cout << spfa(1, mx) << endl; cout << -dis[mx] << endl; // printf("%d\n", -dis[mx + 1]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; work(); return 0; }
POJ 1201 Intervals 差分约束
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。