poj 1201-差分约束+spfa
题意: 在区间[0,50000]上有一些整点,并且满足n个约束条件(u, v, w),即在区间[u, v]上至少有x个整点,问区间[0, 50000]上至少有几个整点。
思路:spfa(邻接表)+差分约束。构造差分约束系统的关键:用dict[i]表示区间[0, i]上的整点数,则约束条件可化为dict[v] - dict[u-1] >= w,即dict[v] >= dict[u-1] + w,为spfa求最长路径。另外还必须挖掘完整两个隐含的约束条件,这也相当重要,即1 >= dict[i] - dict[i-1] >= 0,(dict[i] >= dict[i-1] + 0(正向边)和 dict[i-1] - dict[i] >= -1 (反向边)。因此区间[0, 50000]上至少有几个整点即为dict[i]的最大值,即dict[max_num]的值。
在差分约束系统中如果题目要求是求最小值,就将约束条件转化为">="形式,然后用Bellman_Ford算法求解约束图的最长路径,如果题目要求的是最大值,就将约束条件转化为"<="形式,然后用Bellman_Ford算法求解约束图的最短路径.
代码:
[cpp]
#include <stdio.h>
#define maxN 50005//最大边条数
#define inf 0x7fffffff//最大距离
struct Edge
{
int v, w, next;
}edge[4 * maxN];//边集
int dis[maxN];
bool vis[maxN];
int queue[10 * maxN];
int preEdge[maxN];//同一个顶点的前一条边
int edgeNum,n,maxn;
void addEdge(int u, int v, int w)//添加一条边
{
edge[edgeNum].v = v;
edge[edgeNum].w = w;
edge[edgeNum].next = preEdge[u];
preEdge[u] = edgeNum ++;
}
void spfa()//spaf算法
{
int head = 0, tail = 1;
for (int i = 0; i <= maxn; ++ i)
{
dis[i] = -inf;
}
queue[head] = 0;
dis[0] = 0;
while (head < tail)
{
int u = queue[head];
vis[u] = true;
for (int p = preEdge[u]; p != 0; p = edge[p].next)
{
int v = edge[p].v;
if (dis[v] < dis[u] + edge[p].w)
{
dis[v] = dis[u] + edge[p].w;
if (!vis[v])
{
vis[v] = true;
queue[tail] = v;
tail ++;
/*if (tail == maxN)
{
tail = 0;
}*/
}
}
}
vis[u] = false;
head ++;
/*if (head == maxN)
{
head = 0;
}*/
}
}
int main()
{
scanf("%d", &n);
edgeNum = 1;
maxn = 0; www.zzzyk.com
while (n --)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
if (v + 1 > maxn)
{
maxn = v + 1;
}
addEdge(u, v + 1, w);
}
for (int i = 0; i <= maxn; ++ i)
{
addEdge(i, i + 1, 0);
addEdge(i + 1, i, -1);
}
spfa();
printf("%d\n", dis[maxn]);
return 0;
}
作者:zhang20072844
补充:软件开发 , C++ ,