大佬们瞅瞅我的差分约束系统哪里挂了。。。
  • 板块UVA1723 Intervals
  • 楼主MuYC
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/5 10:09
  • 上次更新2023/11/5 11:59:17
查看原帖
大佬们瞅瞅我的差分约束系统哪里挂了。。。
67817
MuYC楼主2020/10/5 10:09

Rt

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
struct node{int u,v,w;}r[300005];
int start[100001],ls,vis[100005],dis[100005],book[100005];
int m=0,n,Max = 0,Min = 0x3f;
int cmp(node A,node B){return A.u < B.u;}
void add(int u,int v,int w){
	m++;
	r[m].u = u ; r[m].v = v ; r[m].w = w;
}
void SPFA(int s);
int main(){
	cin >> n;
	for (int i = 1 ; i <= n ; i ++){
		int L,R,w;
		cin >> L >> R >> w;
		add (R+1 , L , -w); // T[L] - T[R+1] <= -w 
		Max = max(Max,R+1);
		Min = min(Min,L);
	}
	for(int i = 1 ; i <= Max ; i ++){
		add(i,i-1,0);//T[i-1] - T[i] <= 0
		add(i-1,i,1);//T[i] - T[i-1] <= 1
		add(Max+1,i,0);
	}
	sort ( r+1 , r+1+m , cmp);
	ls = -1;
	for (int i = 1 ; i <= m ; i ++)
		if (ls != r[i].u)ls = r[i].u,start[ls] = i ;
	SPFA(Max+1);
	return 0;
}
void SPFA(int s){
	for (int i = 0 ; i <= Max ; i ++)dis[i] = 0x7ffffff;
	int head = 0 , tail = 1;
	vis[1] = s;
	while (head < tail){
		head++;
		int v = vis[head];
		book[v] = 0;
		for (int i = start[v] ; i <= m && r[i].u == v ; i ++){
			int to = r[i].v ;
			if (dis[to] > dis[v] + r[i].w){
				dis[to] = r[i].w + dis[v];
				if (book[to] != 1)book[to] = 1, tail ++ ,vis[tail] = to;
			}
		}
	}
	cout << dis[Max] - dis[Min];
}
2020/10/5 10:09
加载中...