【POJ 1201】 Intervals（差分约束系统）

11

1716的升级版 把原本固定的边权改为不固定。

Description

Input

Output

Sample Input

5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

Sample Output

6

Source

关于差分约束系统，百度各种大牛博客讲的都非常具体，简单说就是通过不等关系建立约束系统图。然后跑最短路（大于关系则跑最长路）

回到此题，题目要求找出一个最小集合S。满足对于n个范围[ai,bi]，S中存在ci个及ci个以上不同的点在范围内

令Zi表示满足条件的情况下，0~i点至少有多少点在集合内

则Zbi-Zai >= ci

仅仅有这一个条件构造出来的图可能不是全然连通的，所以须要找一些“隐含条件”

不难发现 对于相邻的点 0 <= Zi-Z(i-1) <= 1 保证关系符同样 转化为

Zi-Z(i-1) >= 0

Z(i-1)-Zi >= -1

用这三个关系，就可以构造差分约束系统，然后SPFA或者Bellman跑一趟最长路（满足全部条件）

代码例如以下：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;

const int msz = 1e5;

const int mod = 1e9+7;

const double eps = 1e-8;

struct Edge

{

	int v,w,next;

};

Edge eg[233333];

int head[50050];

bool vis[50050];

int dis[50050];

int tp,st,en;

void Add(int u,int v,int w)

{

	eg[tp].v = v;

	eg[tp].w = w;

	eg[tp].next = head[u];

	head[u] = tp++;

}

int SPFA()

{

	memset(vis,0,sizeof(vis));

	memset(dis,-INF,sizeof(dis));

	queue <int> q;

	dis[st] = 0;

	vis[st] = 1;

	int u,v,w;

	q.push(st);

	while(!q.empty())

	{

		u = q.front();

		q.pop();

		vis[u] = 0;

		for(int i = head[u]; i != -1; i = eg[i].next)

		{

			v = eg[i].v;

			w = eg[i].w;

			if(dis[v] < dis[u]+w)

			{

				dis[v] = dis[u]+w;

				if(!vis[v])

				{

					q.push(v);

					vis[v] = 1;

				}

			}

		}

	}

	return dis[en];

}

int main(int argc,char **argv)

{

	int n;

	int u,v,w;

	while(~scanf("%d",&n))

	{

		tp = 0;

		memset(head,-1,sizeof(head));

		en = 0,st = INF;

		while(n--)

		{

			scanf("%d%d%d",&u,&v,&w);

			Add(u,v+1,w);

			en = max(en,v+1);

			st = min(st,u);

		}

		for(int i = st; i < en; ++i)

		{

			Add(i,i+1,0);

			Add(i+1,i,-1);

		}

		printf("%d\n",SPFA());

	}

	return 0;

}