POJ 1201 Intervals(差分约束 区间约束模版)

关于差分约束详情可阅读:http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

题意:

给定n个区间[L,R], 每个区间至少放w个球, 问最后整个区间最少要放多少个球。

分析:

假设d[i] 是 [1,i] 至少有多少个点被选中, 特殊地, d[0] = 0。 每个区间的描述可以转化为d[R] - d[L-1] >= w。(因为d[L]也要选中, 左闭右闭区间, 所以要减d[L-1])
因为d[i]描述了一个求和函数,所以对于d[i]和d[i-1]其实是有自身限制的,考虑到每个点有选和不选两种状态,所以d[i]和d[i-1]需要满足以下不等式: 0 <= d[i] - d[i-1] <= 1 (即第i个数选还是不选)

这样, 我们就有了3个约束不等式

d[R] - d[L-1] >= w  (1)

d[i] - d[i-1] >= 0      (2)

d[i-1] - d[i] >= -1     (3)

求出d[min-1]到d[max]的最长路, d[max] 就是这个区间最少要放多少个球。

#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,b) for(int i = a; i < b; i++)
#define _rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
const int maxn = + ;
struct edge{
int to , d;
edge(int _to, int _d): to(_to), d(_d){}
};
vector<edge> G[maxn];
/*
差分约束系统
对于每个不等式 x[i] - x[j] >= a[k],对结点 j 和 i 建立一条 j -> i的有向边,边权为a[k],求x[n] - x[1] 的最大值就是求 1 到n的最长路。 假设d[i] 是 [1,i] 至少有多少个点被选中, 特殊地, d[0] = 0;
每个区间的描述可以转化为d[R] - d[L-1] >= w 因为d[i]描述了一个求和函数,所以对于d[i]和d[i-1]其实是有自身限制的,考虑到每个点有选和不选两种状态,
所以d[i]和d[i-1]需要满足以下不等式: 0 <= d[i] - d[i-1] <= 1 (即第i个数选还是不选)
*/ void add_edge(int u, int v, int d){
G[u].push_back(edge(v, d));
}
int n, a, b;
bool vis[maxn];
int dis[maxn];
int spfa(int s){
memset(vis,, sizeof(vis));
for(int i = a; i <= b; i++) dis[i] = -1e9;
queue<int> q;
vis[s] = ;
dis[s] = ;
q.push(s);
while(!q.empty()){
int u = q.front();
for(int i = ; i < G[u].size(); i++){
int v = G[u][i].to, d = G[u][i].d;
if(dis[u] + d > dis[v]){//求最长路
dis[v] = dis[u] + d;
if(!vis[v]){
vis[v] = ;
q.push(v);
}
}
}
vis[u] = ;
q.pop();
}
return dis[b];
}
int main(){
// freopen("1.txt","r", stdin);
while(~scanf("%d", &n)){
a = 1e9 + , b = -1e9 + ; //求这个区间的最小值, 最大值
rep(i,,maxn) G[i].clear();
rep(i,,n){
int L, R, w;
scanf("%d %d %d", &L, &R, &w);
a = min(a, L), b = max(b, R);
add_edge(L-,R,w);//对结点 j 和 i 建立一条 j -> i的有向边,边权为a[k]
}
_rep(i,a,b){
add_edge(i-,i,); //d[i] - d[i-1] >= 0
add_edge(i,i-,-); //d[i] - d[i-1] <= 1 不等式标准化成 d[i-1] - d[i] >= -1
}
puts("");
printf("%d\n",spfa(a-));
}
}
上一篇:【题解】 POJ 1201 Intervals(差分约束)


下一篇:POJ 1201 Intervals【差分约束】