lct切之

const
inf = 1 << 30;
type
splayType = record
rev : boolean;
f,path_f,max,p : longint;
c : array[0..1] of longint;
end;
eType = record
x,y,a,b : longint;
end;
var
e : array[0..100000] of eType;
t : array[0..150000] of splayType;
ans,n,m : longint;

procedure swap(var x,y:longint);var z : longint; begin z := x; x := y; y := z; end;
function min(x,y:longint):longint; begin min := x; if y < x then min := y; end;

procedure reverse(x:longint);
begin
if x = 0 then exit;
t[x].rev := not t[x].rev;
swap(t[x].c[0],t[x].c[1]);
end;

procedure normalize(x:longint);
var
i : longint;
begin
if x = 0 then exit;
if t[x].rev then
begin
t[x].rev := false;
reverse(t[x].c[0]);
reverse(t[x].c[1]);
end;
i := t[x].c[0];
if t[t[x].c[1]].max > t[t[x].c[0]].max then i := t[x].c[1];
if (x > n) and (t[i].max < e[x-n].b) then
begin
i := x; t[x].max := e[x-n].b; t[x].p := x;
end;
t[x].p := t[i].p; t[x].max := t[i].max;
end;

function dd(x:longint):longint;
begin
dd := ord(t[t[x].f].c[1] = x);
end;

procedure sc(x,y,d:longint);
begin
t[y].c[d] := x; t[x].f := y;
end;

procedure cc(x,d:longint);
begin
if t[x].c[d] = 0 then exit;
t[t[x].c[d]].f := 0; t[t[x].c[d]].path_f := x; t[x].c[d] := 0;
end;

procedure rot(x:longint);
var
y,d : longint;
begin
y := t[x].f; d := dd(x);
sc(x,t[y].f,dd(y));
sc(t[x].c[d xor 1],y,d);
sc(y,x,d xor 1);
t[x].path_f := t[y].path_f;
normalize(y);
normalize(x);
end;

procedure splay(x,y:longint);
begin
while t[x].f <> y do
begin
normalize(t[t[x].f].f);
normalize(t[x].f);
normalize(x);
if t[t[x].f].f <> y then
if dd(t[x].f) = dd(x) then rot(t[x].f) else rot(x);
rot(x);
end;
end;

procedure access(x:longint);
var
y : longint;
begin
splay(x,0); normalize(x);
cc(x,1); normalize(x);
while t[x].path_f > 0 do
begin
y := t[x].path_f; splay(y,0);
normalize(y); cc(y,1);
sc(x,y,1); normalize(y);
x := y;
end;
end;

procedure evert(x:longint);
begin
access(x);
splay(x,0);
reverse(x);
end;

function exist(x,y:longint):boolean;
begin
exist := false;
evert(x);
access(y);
splay(x,0);
normalize(x);
while y > 0 do
begin
if y = x then exit(true);
y := t[y].f;
end;
end;

function get(x,y:longint):longint;
begin
evert(x);
access(y);
splay(x,0);
get := t[x].max;
end;

procedure cut(x,y:longint);
begin
evert(y);
access(x);
splay(y,0);
t[y].c[1] := 0; t[x].f := 0; t[x].path_f := 0; normalize(y);
end;

procedure link(x,y:longint);
begin
evert(x);
evert(y);
splay(x,0);
splay(y,0);
normalize(x); sc(y,x,0); normalize(x);
end;

procedure sort(l,r:longint);
var
i,j : longint; x : eType;
begin
i := l; j := r; x := e[(l+r) >> 1];
repeat
while e[i].a < x.a do inc(i);
while x.a < e[j].a do dec(j);
if i <= j then
begin
e[0] := e[i]; e[i] := e[j]; e[j] := e[0];
inc(i); dec(j);
end;
until i > j;
if l < j then sort(l,j);
if i < r then sort(i,r);
end;

procedure init;
var
j,i : longint;
begin
ans := inf;
readln(n,m);
for i := 1 to m do readln(e[i].x,e[i].y,e[i].a,e[i].b);
sort(1,m);
for i := 1 to m do t[i+n].max := e[i].b;
for i := 1 to m do t[i+n].p := i+n;
for i := 1 to m do
begin
if not exist(e[i].x,e[i].y) then
begin
link(e[i].x,i+n);
link(e[i].y,i+n);
end else begin
if get(e[i].x,e[i].y) <= e[i].b then continue;
j := t[e[i].x].p - n;
cut(j+n,e[j].x); cut(j+n,e[j].y);
link(e[i].x,i+n); link(e[i].y,i+n);
end;
if exist(1,n) then ans := min(ans,get(1,n)+e[i].a);
end;
if ans < inf then writeln(ans) else writeln(-1);
end;

begin
init;
end.

http://www.cnblogs.com/JSZX11556/p/5153844.html

P1865魔法森林
Accepted

记录信息

评测状态 Accepted
题目 P1865 魔法森林
递交时间 2015-09-03 14:56:05
代码语言 C++
评测机 VijosEx
消耗时间 11863 ms
消耗内存 11180 KiB
评测时间 2015-09-03 14:56:20

评测结果

编译成功

foo.cpp: In function 'void spfa(int)':
foo.cpp:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < linker[ now ].size() ; i++ )
^

测试数据 #0: Accepted, time = 15 ms, mem = 4084 KiB, score = 5

测试数据 #1: Accepted, time = 6 ms, mem = 4080 KiB, score = 5

测试数据 #2: Accepted, time = 15 ms, mem = 4088 KiB, score = 5

测试数据 #3: Accepted, time = 15 ms, mem = 4232 KiB, score = 5

测试数据 #4: Accepted, time = 37 ms, mem = 4228 KiB, score = 5

测试数据 #5: Accepted, time = 31 ms, mem = 4232 KiB, score = 5

测试数据 #6: Accepted, time = 93 ms, mem = 4784 KiB, score = 5

测试数据 #7: Accepted, time = 78 ms, mem = 4788 KiB, score = 5

测试数据 #8: Accepted, time = 93 ms, mem = 4788 KiB, score = 5

测试数据 #9: Accepted, time = 93 ms, mem = 4780 KiB, score = 5

测试数据 #10: Accepted, time = 1312 ms, mem = 11128 KiB, score = 5

测试数据 #11: Accepted, time = 1218 ms, mem = 11140 KiB, score = 5

测试数据 #12: Accepted, time = 1046 ms, mem = 11132 KiB, score = 5

测试数据 #13: Accepted, time = 1156 ms, mem = 11180 KiB, score = 5

测试数据 #14: Accepted, time = 1375 ms, mem = 11132 KiB, score = 5

测试数据 #15: Accepted, time = 1250 ms, mem = 11132 KiB, score = 5

测试数据 #16: Accepted, time = 1031 ms, mem = 11140 KiB, score = 5

测试数据 #17: Accepted, time = 828 ms, mem = 11132 KiB, score = 5

测试数据 #18: Accepted, time = 1078 ms, mem = 11144 KiB, score = 5

测试数据 #19: Accepted, time = 1093 ms, mem = 11128 KiB, score = 5

Accepted, time = 11863 ms, mem = 11180 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>

using namespace std;

int n , m;
int i;
vector < int > linker[50000 + 2];
vector < int > di[50000 + 2];
vector < int > fi[50000 + 2];

struct edge
{
int x , y , a , b;
};

edge e[100000 + 2];

inline int cmp( edge a , edge b )
{
return a.a < b.a;
}

bool use[50000 + 2];
int dist[50000 + 2];
int now , cur , v;

inline int min( int a , int b )
{
if( a > b )
return b;
return a;
}

inline int max( int a , int b )
{
if( a > b )
return a;
return b;
}

int ans;
queue < int > q;

inline void spfa( int lim )
{
int i;
q.push( 1 );
while( !q.empty() )
{
now = q.front();
q.pop();
use[ now ] = 0;
for( i = 0 ; i < linker[ now ].size() ; i++ )
if( fi[ now ][i] <= lim )
{
cur = linker[ now ][i];
v = di[ now ][i];
if( dist[ cur ] > max( dist[ now ] , v ) )
{
dist[ cur ] = max( dist[ now ] , v );
if( !use[ cur ] )
{
q.push( cur );
use[ cur ] = 1;
}
}
}
}
ans = min( ans , dist[n] + lim );
return;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= m ; i++ )
{
scanf( "%d %d %d %d" , &e[i].x , &e[i].y , &e[i].a , &e[i].b );
linker[ e[i].x ].push_back( e[i].y );
linker[ e[i].y ].push_back( e[i].x );
di[ e[i].x ].push_back( e[i].b );
di[ e[i].y ].push_back( e[i].b );
fi[ e[i].x ].push_back( e[i].a );
fi[ e[i].y ].push_back( e[i].a );
}
sort( e + 1 , e + m + 1 , cmp );
ans = 100000000;
for( i = 2 ; i <= n ; i++ )
dist[i] = 100000000;
dist[1] = 0;
for( i = 1 ; i <= m ; i++ )
if( e[i].a >= ans )
break;
else
{
q.push( e[i].x );
q.push( e[i].y );
spfa( e[i].a );
}
if( ans <= 1000000 )
cout << ans << endl;
else
cout << -1 << endl;
return 0;
}
没有优化的spfa动态加点

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct Tb{
int num,aa,bb,next;
};
Tb a[200001];
int first[100001];
Tb p[100001];
bool vis[100001];
int n,m,ans;
int sou(int v)
{
int j,k;
if(v==n)
{
ans=min(ans,p[v].aa+p[v].bb);
return 0;
}
k=first[v];
while(a[k].num!=0)
{
j=a[k].num;
if(!vis[j])
{
p[j].aa=max(p[v].aa,a[k].aa);
p[j].bb=max(p[v].bb,a[k].bb);
vis[j]=true;
sou(j);
vis[j]=false;
}
k=a[k].next;
}

}
int main()
{
int w1,w2,x,y,k=0;
freopen("p1865.in","r",stdin);
scanf("%d%d",&n,&m);
Tb b;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&x,&y,&w1,&w2);
k++;
a[k].next=first[x];
a[k].num=y;
a[k].aa=w1;
a[k].bb=w2;
first[x]=k;

k++;
a[k].next=first[y];
a[k].num=x;
a[k].aa=w1;
a[k].bb=w2;
first[y]=k;

}
memset(vis,false,true);
ans=12345678;
vis[1]=true;
sou(1);
if(ans==12345678)
printf("-1");
else printf("%d",ans);
return 0;
}

看我Blog:http://niyouzack.blog.163.com/blog/static/237227103201476115514469/

hahaha