poj 1201 Intervals&1716 Integer Intervals差分制約

テーマは1つのシーケンスを求めて、与えられた条件を満たして、その最小の数を求めます
d[i]を[0,i)区間内の答えの個数とし、ここでd[0]=0
タイトルに入力するa,b,cは、d[b+1]–d[a]>=c
意味隠し不等式は、0<=d[i+1]–d[i]<=1,d[i]–d[0]>=0
最小個数を求めるので、0をソースポイントとして最長ルートを求めると、答えはd[n]–d[1]となる
 
1716は、上のcを2に変更すればよい
 

#include <iostream>

#include <vector>

#include <queue>

#include <cstring>

#include <cstdio>

using namespace std;



const int MAX = 50005;

const int INF = 1000000000;



struct edge

{

	int v;

	int cost;

	edge(){}

	edge(int v, int cost)

	{

		this->v = v;

		this->cost = cost;

	}

};



vector<edge> adj[MAX];

queue<int> Q;

bool is_in_queue[MAX];

int dis[MAX];

int _min, _max;

int n;

int cnt[MAX];



void spfa()

{

	while (!Q.empty()) Q.pop();

	int u;

	Q.push(_min);



	memset(is_in_queue, false, sizeof(is_in_queue));

	for (int i = _min; i <= _max+1; i++)

		dis[i] = -INF;



	dis[_min] = 0;

	is_in_queue[_min] = true;

	while (!Q.empty())

	{

		u = Q.front();

		Q.pop();

		is_in_queue[u] = false;



		for (int i = 0; i < adj[u].size(); i++)

		{

			int v = adj[u][i].v;

			int w = adj[u][i].cost;

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

			{

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



				if (!is_in_queue[v])

				{

					Q.push(v);

					is_in_queue[v] = true;

				}		

			}

		}

	}

}

int main()

{

	int a, b, c;

	while (cin >> n)

	{

		_min = INF;

		_max = -1;



		for (int i = 0; i < n; i++)

		{

			scanf("%d%d%d", &a, &b, &c);

			adj[a].push_back(edge(b+1, c));

			_min = min(_min, a);

			_max = max(_max, b);

		}



		for (int i = _min; i <= _max; i++)

		{

			adj[0].push_back(edge(i, 0));

			adj[i].push_back(edge(i+1, 0));

			adj[i+1].push_back(edge(i, -1));

		}



		adj[0].push_back(edge(_max+1, 0));



		spfa();



		cout << dis[_max+1] - dis[_min] << endl;



		for (int i = 0; i <= _max+1; i++)

			adj[i].clear();

	}

	return 0;

}