随便's Blog

Description

将图中的空白部分转化为一个个点点与点之间的边权值等于公共边的边权。这样从右上的点到左下的点中每一条路径都是原图的一个割。所以就转化为了一个求最短路的问题。

这种方法要求图形是已知的规则图形，一般的题目没法用（不然DINIC不就废了╮(╯_╰)╭）

/**************************************************************
    Problem: 1001
    User: 1115825064
    Language: C++
    Result: Accepted
    Time:2980 ms
    Memory:109680 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
const int N=1000100,MOD=3000003;
 
int n,m,f[3*N];
struct D{
    int to,next,w;
}e[6*N];
int head1[3*N],tot=1;
int S,T;
 
void jia(int v,int u,int a)
{
    tot++;e[tot].to=u;e[tot].w=a;e[tot].next=head1[v];head1[v]=tot;
} 
#define LINK(x) for(int i=head1[x];i;i=e[i].next)
 
 
int que[N*3],head=0,tail=1;
bool dian[3*N];
int main()
{
//  freopen("1.txt","r",stdin);
//  freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
     
    T=0,S=2*n*m+1;
    for(int i=0;i<n;++i)
        for(int j=1;j<m;++j)
        {
            int a;
            scanf("%d",&a);
            int u=i*2*m+j,v=u-m;
            if(v<0) v=T;
            if(i==n-1) u=S;
            jia(u,v,a);
            jia(v,u,a);
        }
    for(int i=0;i<n-1;++i)
        for(int j=0;j<m;++j)
        {
            int a;
            scanf("%d",&a);
            int u=i*2*m+j,v=u+m+1;
            if(j==0)u=S;
            if(j==m-1) v=T;
            jia(u,v,a);
            jia(v,u,a);
        }
    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j)
        {
            int a;
            scanf("%d",&a);
            int u=(i-1)*2*m+j,v=u+m;
            jia(u,v,a);
            jia(v,u,a);
        }
         
    que[1]=0;
    dian[0]=1;
//  for(int i=1;i<3*N;++i) f[i]=100000000;
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    while(head!=tail)
    {
        head%=MOD;
        head++;
        int x=que[head];
        dian[x]=0;
        LINK(x) if(f[x]+e[i].w<f[e[i].to])
        {
            f[e[i].to]=f[x]+e[i].w;
            if(dian[e[i].to]==0) 
            {
                    dian[e[i].to]=1;
                    tail%=MOD;
                    que[++tail]=e[i].to;
            }
         
        }
    }
    printf("%d",f[S]);
} 

这个文档挺不错的，挂个链接

http://wenku.baidu.com/view/5a7df375a417866fb84a8e54.html

题目：一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身

树链剖分;

每一个点记录子树最大的儿子节点，标记重边。对于每个重边形成的链维护线段树。一棵树上的多个链可以放到一颗线段树中，注意不要弄混就可以了。    Problem: 1036

    User: 1115825064
    Language: C++
    Result: 正确
    Time:2680 ms
    Memory:6472 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
 
using namespace std;
 
const int N=30005;
 
int n;
 
struct D{
    int fa,son,dep,top,size,w;
}a[N];
int tree1[N],pre[N],tot_t=0;
struct L{
    int to,next;
}e[N*2];
int head[N],tot_l=1;
void jial(int u,int v)
{
    e[++tot_l].to=v;e[tot_l].next=head[u];head[u]=tot_l;
}
#define link(x) for(int i=head[x];i;i=e[i].next)
 
struct T{
    int l,r,sum,Max;
}trees[4*N];
 
void dfs1(int wz,int f,int de)//第一次深搜记录父节点·重儿子和深度。
{
    a[wz].fa=f;
    a[wz].dep=de;
    a[wz].size=1;
    int s=1,son=-1e9,p=0;   
    link(wz) if(e[i].to!=f)
    {
        dfs1(e[i].to,wz,de+1);
        a[wz].size+=a[e[i].to].size;
        if(!a[wz].son||a[a[wz].son].size<a[e[i].to].size)
        {
            a[wz].son=e[i].to;
        }
    }
    return ;
}
void dfs2(int wz,int top)//记录重链的最上面的节点。将每条链加入数组中。（要保证同一条链连续）
{
    a[wz].top=top;tree1[wz]=++tot_t;pre[tree1[wz]]=wz;
    if(a[wz].son==0)    return ;
    dfs2(a[wz].son,top);
    link(wz)    if(e[i].to!=a[wz].son&&e[i].to!=a[wz].fa)
        dfs2(e[i].to,e[i].to);
    return ;
}
void build(int i,int l,int r)//建树
{
    trees[i].r=r;
    trees[i].l=l;
    if(l==r)
    {
        trees[i].sum=trees[i].Max=a[pre[l]].w;
        return ;
    }
    build(i*2,l,(l+r)/2);
    build(i*2+1,((l+r)/2)+1,r);
    trees[i].sum=trees[i*2].sum+trees[i*2+1].sum;
    trees[i].Max=max(trees[i*2].Max,trees[i*2+1].Max);
    return ;
}
 
void jia(int wz,int u,int t)
{
     
    if(trees[wz].l==trees[wz].r)
    {
        trees[wz].sum+=t;
        trees[wz].Max+=t;
        return ;
    }
    int mid=(trees[wz].l+trees[wz].r)/2;
    if(u<=mid)
        jia(wz*2,u,t);
    else
        jia(wz*2+1,u,t);
    trees[wz].Max=max(trees[wz*2].Max,trees[wz*2+1].Max);
    trees[wz].sum=trees[wz*2].sum+trees[wz*2+1].sum;
    return ;
}
 
int fi_Max(int i,int ll,int rr)
{
    if(ll<=trees[i].l&&rr>=trees[i].r)
    {
        return trees[i].Max;
    }
    int mid=(trees[i].l+trees[i].r)/2;
    int p=-1e9;
    if(ll<=mid)
        p=fi_Max(i*2,ll,rr);
    if(rr>mid)
        p=max(p,fi_Max(i*2+1,ll,rr));
    return p;
}
int fi_sum(int i,int ll,int rr)
{
    if(ll<=trees[i].l&&rr>=trees[i].r)
    {
        return trees[i].sum;
    }
    int mid=(trees[i].l+trees[i].r)/2;
    int p=0;
    if(ll<=mid)
        p+=fi_sum(i*2,ll,rr);
    if(rr>mid)
        p+=fi_sum(i*2+1,ll,rr);
    return p;
}
 
int q_Max(int u,int v)
{
    int fu=a[u].top,fv=a[v].top;
    if(fu==fv)
    {
        if(tree1[u]>tree1[v]) swap(u,v);
        return fi_Max(1,tree1[u],tree1[v]);
    }
    if(a[fu].dep<a[fv].dep)
    {
        swap(v,u);
        swap(fu,fv);
    }
    int p=q_Max(a[fu].fa,v);
    p=max(p,fi_Max(1,tree1[fu],tree1[u]));
    return p;
     
}
int q_sum(int u,int v)
{
    int fu=a[u].top,fv=a[v].top;
    if(fu==fv)
    {
        if(tree1[u]>tree1[v]) swap(u,v);
        return fi_sum(1,tree1[u],tree1[v]);
    }
        if(a[fu].dep<a[fv].dep)
    {
        swap(v,u);
        swap(fu,fv);
    }
    int p=q_sum(a[fu].fa,v);
    p+=fi_sum(1,tree1[fu],tree1[u]);
    return p;
} 
int main()
{
//  freopen("1.txt","r",stdin);
     
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        jial(u,v);
        jial(v,u);
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i].w);
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    char ss[10];
    int Q1,u,v;
    scanf("%d",&Q1);
 
    while(Q1--)
    {
        scanf("%s%d%d",ss,&u,&v);
        if(ss[0]=='C')
        {
            jia(1,tree1[u],v-a[u].w);
            a[u].w=v;
        }
        if(ss[1]=='M')
        {
            printf("%d\n",q_Max(u,v));
        }
        if(ss[1]=='S')
        {
            printf("%d\n",q_sum(u,v));
        }
    }
    return 0;
}

敲了二百多行，写着写着就凌乱了结果交了5遍。感谢这个题，我愉快（chedan）的学会了造数据。orz

题目：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

平衡树的模板题，借这个题整理一下平衡树；

核心是维护一颗二叉树的中序遍历，以中序遍历的先后表示维护的序列。

对于上图，两棵树的中序遍历均c2.B.c3.A.c1，故可以用这种方式交换B,A的位置。

对于插入x，只需要找到与x最接近的点P，然后根据大小插入左或右儿子。

5，6 操作只需将x旋到根节点，其左子树的最右边的节点和右子树的最左边的节点就是前驱与后驱。这里要注意x不一定在树中，在操作之前需要先插入x，在最后删去。树中也可能有多个x点，查询时需要找到第一位或最后一位。

3，4 操作维护每个节点下共有多少个节点就可快速得出来，每次旋转，两个节点的子树没有改变，所以只需要维护交换的两节点A,B。

删除x，将x点的前一个点旋到根，再将x的后一个点旋到根节点的右儿子处，在中序遍历中，左边的点都比该点靠前，右边的点比该点靠后。所以之后x就被旋到后一个点的左儿子的位置。只要将左儿子的指针归零就可以了。在删除时，如果x为第一个或最后一个就会没有前驱或后驱，所以开始是要先向树中加入一个极大值和一个极小值。

/**************************************************************
    Problem: 3224
    User: 1115825064
    Language: C++
    Result: 正确
    Time:644 ms
    Memory:3228 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
 
using namespace std;
 
struct D{
    int w,lc,rc,size,fa;
}a[100005];
int tot=0,root=0;
 
 
void update(int x)
{
    a[x].size=a[a[x].lc].size+a[a[x].rc].size+1;
}
 
void xuan1(int x)
{
    int y=a[x].fa;
    int z=a[y].fa;
    a[a[x].lc].fa=y;
    a[y].rc=a[x].lc;
    a[x].lc=y;
    a[x].fa=z;
    a[y].fa=x;
    if(a[z].lc==y)  a[z].lc=x;
    else    a[z].rc=x;
    update(y);
    update(x);
}
void xuan2(int x)
{
    int y=a[x].fa;
    int z=a[y].fa;
    a[a[x].rc].fa=y;
    a[y].lc=a[x].rc;
    a[x].rc=y;
    a[x].fa=z;
    a[y].fa=x;
    if(a[z].lc==y)  a[z].lc=x;
    else    a[z].rc=x;
    update(y);
    update(x);
}
void splay(int x,int wz)
{
    while(a[x].fa!=wz)
    {
        int y=a[x].fa;
        if(a[y].lc==x)  xuan2(x);
        else    xuan1(x);
      
    }
    if(wz==0)   root=x;
}
 
void new_node(int fa,int w,int &x)
{
    x=++tot;
    a[tot].fa=fa;
    a[tot].w=w;
}
 
int search(int x)
{
    int i,j=root;
    while(j)
    {
        i=j;
        if(a[j].w>x) j=a[j].lc;
        else    j=a[j].rc;
    }
    return i;
}
 
void jia(int x)
{
    if(root==0)
    {
        new_node(0,x,root);
        return ;
    }
    int y=search(x);
    if(x<a[y].w) new_node(y,x,a[y].lc);
    else    new_node(y,x,a[y].rc);
    splay(tot,0);
    update(root);
}
 
int  get(int x)
{
    int ans=tot+1;
    int i=root;
    while(i)
    {
        if(a[i].w==x)
            ans=i;
        if(a[i].w>=x)    i=a[i].lc;
        else    i=a[i].rc;
    }
    if(ans==tot+1)  return -1;
    else    return ans;
}
int max(int x)
{
    while(a[x].rc)  x=a[x].rc;
    return x;
}
int min(int x)
{
    while(a[x].lc)  x=a[x].lc;
    return x;
}
 
void shan(int x)
{
    int y=get(x);
    if(y==-1)   return ;
    splay(y,0);
    int ll=max(a[y].lc),rr=min(a[y].rc);
    splay(ll,0);
    splay(rr,root);
    a[rr].lc=0;
    update(rr);
    update(ll);
}
int find(int x)
{
    int y=get(x);
    splay(y,0);
    return a[a[y].lc].size;
}
int findth(int x,int wz)
{
    if(x==a[a[wz].lc].size+1)   return a[wz].w;
    if(x<=a[a[wz].lc].size)  return findth(x,a[wz].lc);
    else    return findth(x-a[a[wz].lc].size-1,a[wz].rc);
}
int qian(int x)
{
    jia(x);
    int y=get(x);
    splay(y,0);
    int ans=max(a[y].lc);
    shan(x);
    return a[ans].w;
}
int hou(int x)
{
    jia(x);
    int ans=min(a[tot].rc);
    shan(x);
    return a[ans].w;
}
 
void B(int x)
{
    if(a[x].lc!=0)  B(a[x].lc);
    printf("%d ",a[x].w);
    if(a[x].rc!=0)  B(a[x].rc);
    return ;
}
 
int main()
{
//  freopen("1.txt","r",stdin);
    int T;
    scanf("%d",&T);
    jia(-10000010);
    jia(10000010);//预处理加入极大值和极小值。
    while(T--)
    {
        int k,x;
        scanf("%d%d",&k,&x);
        if(k==1)    jia(x);
        if(k==2)    shan(x);
        if(k==3)    printf("%d\n",find(x));
        if(k==4)    printf("%d\n",findth(x+1,root));//注意树中多了两个元素。
        if(k==5)    printf("%d\n",qian(x));
        if(k==6)    printf("%d\n",hou(x));  //B(root);printf("\n");
    }
     
 
    return 0;
}