[Sdoi2010 大陆争霸]二叉堆、拓扑序、畸形最短路

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1922
【算法分析】
这个显然必须按照”保护图“的拓扑序来搞。
然后我就模拟那个”保护图“拓扑的过程。
不过期间用最小堆来存放结点的d[i]值。
堆中存放的都是入度为0，且尚未扩展的点。
然后每次取堆顶元素拿出来扩展。
扩展方法如下。
1、
首先把”保护图“中的边弄掉。（其实就是拓扑排序的过程）
然后如果出现可新加入的点，那么update一下他，然后把他放入堆。
update(i)的意思是：d[i]=min(max(limit,d[x]+w)) 其中limit为当前点的d值。
x为在”时间图“中有边x->i的点。w就是该边对应的权值了。
2、
在”时间图“里扩展，假如有我能到的点，而且他的入度以为0，那么可以min一下我走过去的时间。

然后最后输出d[n]。
实际上第一种扩展方式是第二种的漏掉的补充，YY一下就能明白。
【时间复杂度】O((n+m) lg n)
【其它】
泪奔。。。好久没排过第一了。时间是最快的。。。当然，其实挺接近。
然后最后一个是我徒弟~
他的方法完全暴力。
k次spfa，每次判整个d数组是否和前一次的不同，然后拓扑扩展一下，将本次在队列里的点的保护去除。
Orz。。。这样的都能过。。。
1 23953 edward_mj 2392K 326MS G++ 3.06K 2010-05-17 22:02:49 2 23587 nehzilrz 12700K 373MS G++ 1.29K 2010-05-16 13:51:06 3 23691 gaoxin 13488K 466MS Pascal 1.18K 2010-05-16 19:11:12 4 23360 oimaster 1060K 513MS G++ 1.56K 2010-05-15 15:50:58 5 23339 jsn1993 1244K 591MS G++ 1.10K 2010-05-15 07:53:14 6 23184 root 45784K 1152MS G++ 1.14K 2010-05-14 13:40:08 7 23188 FDhyc 45784K 1230MS G++ 1.14K 2010-05-14 13:56:02 8 23936 54525871 2064K 2013MS Pascal 2.48K 2010-05-17 21:12:32 【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
typedef __int64 lld;
const int E=1000005;
const int N=3005;
const int INF=1000000000;
int n,m;
int du[N],zz[N];
lld d[N];

struct edge{int x,y,w;edge *next;};
struct Link_t{
int e;
edge sp[E],*ls[N];
void init(){
e=0;
for (int i=0;i }

void add(int x,int y,int w){
e++;
sp[e].x=x; sp[e].y=y; sp[e].w=w; sp[e].next=ls[x];
ls[x]=&sp[e];
}
}Graph,Protect,Graphop;

struct Heap_t{
int tot,a[N],tmp;

void swap(int x,int y){
tmp=a[x]; a[x]=a[y]; a[y]=tmp;
zz[a[x]]=x; zz[a[y]]=y;
}

void up(int k){
while (k>1 && d[a[k/2]]>d[a[k]]){
swap(k/2,k);
k/=2;
}
}

void down(int k){
int p;
while (k*2<=tot){
p=k*2;
if (p+1<=tot && d[a[p+1]] if (d[a[p]] swap(p,k);
k=p;
}else break;
}
}

void ins(int key){
a[++tot]=key;
zz[key]=tot;
up(tot);
}

void del(){
swap(1,tot);
zz[a[tot]]=0;
tot–;
if (tot<1) return;
down(1);
}

void repair(int p){
up(p);
down(p);
}
}heap;

void input(){
Graph.init();
Protect.init();
Graphop.init();
memset(du,0,sizeof(du));
scanf("%d%d",&n,&m);
for (int i=1,x,y,w;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
Graph.add(x,y,w);
Graphop.add(y,x,w);
}
for (int i=1,Num,x,j;i<=n;i++){
scanf("%d",&Num);
for (j=1;j<=Num;j++){
scanf("%d",&x);
Protect.add(x,i,0);
du[i]++;
}
}
}

void update(int p,lld limit){
for (edge *t=Graphop.ls[p];t;t=t->next)
if (max(d[t->y]+t->w,limit) d[p]=max(d[t->y]+t->w,limit);
}

void topsort(){
int i;
edge *t;

for (i=1;i<=n;i++) d[i]=(lld)(INF)*INF;
d[1]=0;
heap.tot=0;

for (i=1;i<=n;i++)
if (!du[i]) heap.ins(i);

while (heap.tot>0){
int x=heap.a[1];
heap.del();
for (t=Protect.ls[x];t;t=t->next){
du[t->y]–;
if (!du[t->y]){
update(t->y,d[x]);
heap.ins(t->y);
}
}
for (t=Graph.ls[x];t;t=t->next)
if (!du[t->y] && d[t->y]>d[t->x]+t->w){
d[t->y]=d[t->x]+t->w;
heap.repair(zz[t->y]);
}
}
}

int main(){
input();
topsort();
printf("%I64dn",d[n]);
return 0;
}