20180702模板

18:42:08 isap
19:10:17 错误2次后AC

isap要注意，反向遍历时只做边权==0可能会更快
错误解决方法：在样例点编号前加上1，比如4->14，就能避免前向星不熟练等问题(尤其注意前向星的下标)

19:16:28 splay
19:55:53 8分
20:21:49 100分
错误1次后AC
错误统计：1.rotate的先后顺序  2.getpre和getsuc不能混合调用（记得长眼睛） 3.rank里面ans记得+1  4.splay里面记得递归splay(′д｀ )…彡…彡
解决方法：构造一条链检验splay有没有写错。同时使用各种函数。


////isap
#include<cstdio>
#include<cstring>
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=NULL;
    }
}e[410000];
int cnt=-1,head[10100];
void add(int from,int to,int v)
{
    e[++cnt]=edge(to,v,head[from]);
    head[from]=cnt;
    e[++cnt]=edge(from,0,head[to]);
    head[to]=cnt;
}
int S,T,n;
int sum=0,gap[10100];
int d[10100],pre[10100];
void bfs()
{
    int q[10100],l=0,r=0;
    q[++r]=T;
    d[T]=1;
    gap[1]=1;
    while(l<r)
    {
        int k=q[++l];
        for(int i=head[k];~i;i=e[i].nxt)
            if(!d[e[i].n])
            {
                d[e[i].n]=d[k]+1;
                gap[d[e[i].n]]++;//注意这里的下标
                q[++r]=k;
            }
    }
}
int cur[10100];
void isap()
{
    for(int i=1;i<=n;i++)
        cur[i]=head[i];
    memset(gap,0,sizeof(gap));
    memset(d,0,sizeof(d));
    memset(pre,-1,sizeof(pre));
    bfs();
    gap[0]=998244353;
    int s=S;
    while(d[S]<=n)
    {
        if(s==T)
        {
            int p=pre[s],minn=998244353;
            while(~p)
            {
                minn=minn<e[p].v?minn:e[p].v;
                p=pre[e[p^1].n];
            }
            sum+=minn;
            p=pre[s];
            while(~p)
            {
                e[p].v-=minn;
                e[p^1].v+=minn;
                p=pre[e[p^1].n];
            }
            s=S;
        }
        int flag=0;
        for(int i=cur[s];~i;i=e[i].nxt)
            if(e[i].v&&d[e[i].n]+1==d[s])
            {
                pre[e[i].n]=i;
                cur[s]=e[i].nxt;
                s=e[i].n;
                flag=1;
                break;
            }
        if(flag==0)
        {
            int tmp=d[s];
            d[s]=n+1;
            for(int i=head[s];~i;i=e[i].nxt)
                if(e[i].v)
                    d[s]=d[s]<d[e[i].n]+1?d[s]:d[e[i].n]+1;
            gap[tmp]--;
            gap[d[s]]++;
            if(gap[tmp]==0)
                return;
            cur[s]=head[s];
            if(s!=S)
                s=e[pre[s]^1].n;
        }
    }
}
int main()
{
    int m,u,v,w;
    scanf("%d%d%d%d",&n,&m,&S,&T);
    memset(head,-1,sizeof(head));

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    isap();
    printf("%d\n",sum);
    return 0;
}


////splay
#include<cstdio>
#include<cstring>
struct node
{
    int key,w,num;
    node *s[2];
    node(int key)
    {
        this->key=key;
        w=1;
        num=1;
        s[0]=NULL;
        s[1]=NULL;
    }
    node()
    {
        s[0]=NULL;
        s[1]=NULL;
    }
    int getw()
    {
        if(!this)
            return false;
        return w;
    }
    int getd(int x)
    {
        if(x==key)
            return -1;
        return x>key;
    }
    void maintain()
    {
        w=num+s[1]->getw()+s[0]->getw();
    }
}*root=NULL;
void Rotate(node *&rt,int d)
{
    node *tmp=rt->s[d];
    rt->s[d]=tmp->s[d^1];
    tmp->s[d^1]=rt;//顺序理清楚
    rt->maintain();
    tmp->maintain();
    rt=tmp;
    return;
}
void splay(node *&rt,int x)
{
    int d1=rt->getd(x);
    if(d1==-1)
        return;
    int d2=rt->s[d1]->getd(x);
    if(d2==-1)
    {
        Rotate(rt,d1);
        return;
    }
    splay(rt->s[d1]->s[d2],x);//////////要记得加。。。
    if(d1==d2)
    {
        Rotate(rt,d1);
        Rotate(rt,d1);
    }
    else
    {
        Rotate(rt->s[d1],d2);
        Rotate(rt,d1);
    }
    return;
}
void Insert(node *&rt,int x)
{
    if(!rt)
    {
        rt=new node(x);
        return;
    }
    int d=rt->getd(x);
    if(d==-1)
    {
        rt->num++;
        rt->w++;
        return;
    }
    Insert(rt->s[d],x);
    rt->maintain();
    return;
}
int getm(node *rt,int d)
{
    if(rt->s[d]==NULL)
        return rt->key;
    return getm(rt->s[d],d);
}
void Delete(node *&rt,int x)
{
    splay(rt,x);
    //把s旋到根上
    if(rt->num>1)
    {
        rt->num--;
        rt->w--;
        return;
    }
    if(rt->s[0])//左孩子
    {
        int k=getm(rt->s[0],1);
        splay(rt->s[0],k);
        rt->s[0]->s[1]=rt->s[1];
        rt=rt->s[0];
        rt->maintain();
    }
    else if(rt->s[1])
    {
        int k=getm(rt->s[1],0);
        splay(rt->s[1],k);
        rt->s[1]->s[0]=rt->s[0];
        rt=rt->s[1];
        rt->maintain();
    }
    else
        rt=NULL;
}
int ans=0,num;
int Rank(node *rt,int x)//排名第几
{
    int d=rt->getd(x);
    if(rt->s[d]==NULL)
    {
        num=rt->key;
        return 0;
    }

    if(d==-1)
    {
        num=rt->key;
        return ans+1+rt->s[0]->getw();//要加getw()
    }
	
    if(d==0)
        return Rank(rt->s[d],x);
    else
        return rt->s[0]->getw()+rt->num+Rank(rt->s[d],x);
}
int Rankn(node *rt,int x)//排名为多少的是几
{
    if(rt->s[0]->getw()>=x)
        return Rankn(rt->s[0],x);
    else if(rt->s[0]->getw()+rt->num>=x)
        return rt->key;
    else
        return Rankn(rt->s[1],x-(rt->s[0]->getw()+rt->num));
}
int pre=-999999999,suc=999999999;
void getpre(node *rt,int x)
{
    if(!rt)
        return;
    if(rt->key<x)
        pre=pre>rt->key?pre:rt->key;
    int d=rt->getd(x);
    if(d==-1)
        d++;
    getpre(rt->s[d],x);
    return;
}
void getsuc(node *rt,int x)
{
    if(!rt)
        return;
    if(rt->key>x)
        suc=suc<rt->key?suc:rt->key;
    int d=rt->getd(x);
    if(d==-1)
        d+=2;
    getsuc(rt->s[d],x);//不要搞混了
    return;
}
int main()
{
    int n,op,x,tmp;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&op,&x);
        if(op==1)
        {
            Insert(root,x);
            splay(root,x);
        }
        else if(op==2)
            Delete(root,x);
        else if(op==3)
        {
            ans=0;
            printf("%d\n",Rank(root,x));
            splay(root,num);
        }
        else if(op==4)
        {
            tmp=Rankn(root,x);
            printf("%d\n",tmp);
            splay(root,tmp);
        }
        else if(op==5)
        {
            pre=-999999999;
            getpre(root,x);
            printf("%d\n",pre);
            splay(root,pre);
        }
        else
        {
            suc=999999999;
            getsuc(root,x);
            printf("%d\n",suc);
            splay(root,suc);
        }
    }
    return 0;
}