Codeforces Round #712 (Div. 1) C. Travelling Salesman Problem

题目链接：

http://codeforces.com/contest/1503/problem/C

Solution：

考虑你的路径本质上是一个由有向边组成的环，求环上的边权和，所以起点并不重要

每个环的边权(max(c_i,a_j-a_i)),注意到(c_i)不依赖于其他点，考虑提出来,边权可以化成(c_i+max(c_i,a_j-a_i-c_i))

那么答案就是(sum c_i+sum max(0,a_j-a_i-c_i))

前半部分直接算就是了，考虑后半部分，也就是如何安排环上点的顺序

显然任意一种方案的路径都可以拆分为以某一点为起始，到(a_i)最大的点，再回到起点。这样拆分有什么好处呢？

注意到从(a_i)值大的点走到小的，不会产生花费

也就是说走到最大点后，按(a_i)降序走一遍未经过的点回起点，不会产生任何花费

这样我们就只需要考虑前半段，也就是如何走到(a_i)最大的点就好了

当(a_j>a_i+c_i)时也不会产生花费

所以我们以(a_i)为关键字升序排序，去求从首走到尾的最小花费。

考虑走到某一个点(j)，如果前面存在一个点(i),满足(a_j<a_i+c_i),那我可以先到(i)再到(j)，也就是说我可以考虑不花费任何代价走到(j)，否则需要额外花费代价去扩展，代价为(a_j-max(a_k+c_k))((k)表示所有在(j)前面的点)。

过程可以设计为:从最小点出发，走到最大点，当在某一点(i)时，直接走到(i)后面(a)最大且值小于(max（a_k+c_k）)的点(q)((k)表示所有在(i)前面的点)，其中(i)到(q)上的所有点我都可以免费的扩展到。然后再从(q)出发重复这个过程，如果没有符合条件的(q),那么就需要花费代价扩展到(q)的下一个点

我们排序后直接从小到大(O(n))扫一遍，过程中维护下已经扩展了的点中的(max(a_i+c_i)),即可

#include<bits/stdc++.h>
using namespace std;
struct city{
	long long a,c;
}ct[100005];
int n;
long long ans=0;
bool cmp(city x,city y)
{
	if(x.a<y.a)
	   return true;
	return false;   
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&ct[i].a,&ct[i].c);	
	sort(ct+1,ct+1+n,cmp);
	long long mx=0;
	for(int i=1;i<=n-1;i++)
	{
		mx=mx>ct[i].a+ct[i].c?mx:ct[i].a+ct[i].c;
		ans+=ct[i].c;
		if(ct[i+1].a>mx)
			ans+=ct[i+1].a-mx;	
	}
	ans+=ct[n].c;
	printf("%lld",ans);	
	return 0;
}