题目描述
Description
Farmer John决定为他的N头排列好的奶牛（1 <= N<= 200,000）做一张全景合照。这N头奶牛分别以1…N进行编号。他一共拍了M（1<= M <=100,000）张相片，每张相片都只包含有一部分位置连续的奶牛：第i张照片涵盖着编号从a_i到b_i的所有奶牛。当然，这些照片合起来并不保证包含所有的牛。
Farmer John拍摄完所有的相片后，注意到一个很有趣的现象：他拍的每张照片中有且仅有一只奶牛身上有斑点。 FJ知道他的奶牛中有一部分是身上有斑点的，但他从来没有数过这种奶牛的数目。请根据FJ的这些照片，确定可能出现的斑点牛的最大的数目；若从FJ的照片中无法推测斑点牛的数目，则输出-1。
Input
第1行：包含两个整数N、M。
第2… M+1… i +1行：每行包含两个整数a_i和b_i。
Output
输出仅一行，要求输出FJ根据他的照片所能推测出的斑点牛的最大数目；若无法推测这些奶牛的数目，则输出-1。
Sample Input
5 3
1 4
2 5
3 4
Sample Output
1
Data Constraint
1 <= N<= 200,000
前言
其实这题正解是dp
而且100分也没有用到dij
差分约束
形如b-a≤c的不等式，求最大的b-a
（多个的情况类似）
显然a+c≥b，和最短路的性质
dis[u]+len≥dis[v] （u–>v）类似
而当有多个约束时，如b-a≥c、b-a≥d，
则b最大为min(a+c,a+d)，也和最短路类似
所以对于每个b-a≥c，从点a向点b连一条权值为c的边，最后跑一边最短路就是最大值
（最小值貌似反过来就行了）
这道题要求最后选的总点数最大，也就是n的前缀和sum[n]最大
因为每个位置可放可不放，所以
0≤sum[i]-sum[i-1]≤1
从i-1向i连一条值为1的边，从i向i-1连一条值为0的边
因为给定的区间内有且仅有一个，所以
1≤sum[b]-sum[a-1]≤1
从a-1向b连一条值为1的边，从b向a-1连一条值为-1的边
然后跑最短路
dijkstra
初三升高一还不会dij就退役吧（指自己）
和prim做法类似，每次找一个最小点加进去，然后更新相连的点距离
加个普通堆就可以做到O(n logm~m logm)（最坏情况下每加一条边都会丢一次堆）
但有些无良题目（如bzoj3040）会卡普通堆，所以可以加斐波那契堆/配对堆之类的来优化
反正我都不会
然而dij并不能跑负权边（不止是负环），所以。。。
code
只有60分
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
using namespace std;
int a[600001][3];
int ls[200001];
int f[200001];
struct type{
int x,y;
} heap[200001],Get;
int n,m,i,j,k,l,len,h,t,Len;
void New(int x,int y,int z)
{
++len;
a[len][0]=y;
a[len][1]=ls[x];
a[len][2]=z;
ls[x]=len;
}
void swap(type &x,type &y)
{
type z=x;
x=y;
y=z;
}
void put(int t,int id)
{
int i;
++Len;
heap[Len].x=t;
heap[Len].y=id;
i=Len;
while (i>1 && heap[i/2].x>heap[i].x)
{
swap(heap[i/2],heap[i]);
i/=2;
}
}
void get()
{
int i,j;
Get=heap[1];
heap[1]=heap[Len--];
i=1;
j=i*2;
if (i*2<Len && heap[j].x>heap[j+1].x)
++j;
while (i*2<=Len && heap[i].x>heap[j].x)
{
swap(heap[i],heap[j]);
i=j;
j=i*2;
if (i*2<Len && heap[j].x>heap[j+1].x)
++j;
}
}
int main()
{
scanf("%d%d",&n,&m);
fo(i,1,n)
{
New(i-1,i,1);
New(i,i-1,0);
}
fo(i,1,m)
{
scanf("%d%d",&j,&k);
New(j-1,k,1);
New(k,j-1,-1);
}
memset(f,255,sizeof(f));
Len=0;
f[0]=0;
for (i=ls[0]; i; i=a[i][1])
put(a[i][2],a[i][0]);
fo(i,1,n)
{
get();
while (f[Get.y]!=-1)
get();
f[Get.y]=Get.x;
for (j=ls[Get.y]; j; j=a[j][1])
put(f[Get.y]+a[j][2],a[j][0]);
}
printf("%d\n",f[n]<0?-1:f[n]);
}
spfa+SLF
SLF=Small Label First
实现很简单，每次加入一个点到队尾时与队头比较，如果更优就交换
为什么放在这里，是因为在某些图上跑spfa有奇效
比如从20s到0.2s
但好像可以被卡成指数级
如果一个点被走超过100次，那么就出现了负环
code
100分
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define Len 10000000
using namespace std;
int a[600001][3];
int ls[200001];
int f[200001];
int b[200001];
int d[Len+1];
bool bz[200001];
int n,m,i,j,k,l,len,h,t,tot;
void New(int x,int y,int z)
{
++len;
a[len][0]=y;
a[len][1]=ls[x];
a[len][2]=z;
ls[x]=len;
}
void swap(int &x,int &y)
{
int z=x;
x=y;
y=z;
}
int main()
{
scanf("%d%d",&n,&m);
fo(i,1,n)
{
New(i-1,i,1);
New(i,i-1,0);
}
fo(i,1,m)
{
scanf("%d%d",&j,&k);
New(j-1,k,1);
New(k,j-1,-1);
}
memset(f,127,sizeof(f));
f[0]=0;
h=0;
t=1;
d[1]=0;
bz[0]=1;
b[0]=1;
while (h<t)
{
for (i=ls[d[++h]]; i; i=a[i][1])
if (f[a[i][0]]>f[d[h]]+a[i][2])
{
f[a[i][0]]=f[d[h]]+a[i][2];
++b[a[i][0]];
if (b[a[i][0]]>100)
{
printf("-1\n");
exit(0);
}
if (!bz[a[i][0]])
{
bz[a[i][0]]=1;
if (t>=Len) continue;
d[++t]=a[i][0];
if (f[d[t]]<f[d[h+1]])
swap(d[h+1],d[t]);
}
}
bz[d[h]]=0;
}
printf("%d\n",f[n]<0?-1:f[n]);
}
|
转播
