[POJ 2762] 弱连通分量

题意:

给定N个点,E条边的有向图,问图中是否任意两个点u,v都有

(u能到达v)or(v能到达u)

分析:

首先环内的肯定是满足的,所以先缩点。

然后剩下一棵树。

那么从根节点(即缩点后没有入度的点)出发,假设一路走下去是一条链的话(即树没有分叉),而且所有的点都能走到,那么就满足性质。

证明:

1、如果有分叉的话,分叉两边的点不能到达对方。

2、入度为0的点不可能没有,因为已经缩点,不存在环了。

3、入度为0的如果>1,那么两个入度为0的点不能到达对方。

所以,结论就是,只有所有收缩后的点成一长链,才能满足性质。

插曲:

Tarjan居然写错了= =,真想抽自己一下

code:

#include

[SGU 242] 网络流

题意:

有N个学生,可以被分配去M个学校,给出哪些学生能去哪些学校,

求一个解:每间学校都分到>=2个学生的方案。

分析:

cai0715用上下界做。。。其实不用这么麻烦= =

连边(s,i,1) i为学生

连边(i,j,1) j为学校

连边(j,T,2)

然后最大流即可。

插曲:

PE到2B,原来SGU的PE有可能是Runtime ERROR。原来我数组没开够

code:

#include #include #define N 100000
struct gtp{int x,y,c,next,op;}g[N];
int e,n,m,ls[N],flow,cur[N],fa[N],d[N],num[N],list[N][3];

void add(int x,int y,int c){
    e++;
    g[e].x=x;
    g[e].y=y;
    g[e].c=c;
    g[e].next=ls[x];
    ls[x]=e;
    g[e].op=e+1;
   
    e++;
    g[e].x=y;
    g[e].y=x;
    g[e].c=0;
    g[e].next=ls[y];
    ls[y]=e;
    g[e].op=e-1;
}   

void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        add(0,i,1);
        int num,x;
        scanf("%d",&num);
        for (int j=1;j<=num;j++){
            scanf("%d",&x);
            add(i,n+x,1);
        }
    }
    for (int i=1;i<=m;i++) add(i+n,n+m+1,2);
}   

void relabel(int k){
    int min=n+m+1;
    cur[k]=ls[k];
    for (int t=ls[k];t!=0;t=g[t].next)
        if (g[t].c>0 && d[g[t].y]    d[k]=min+1;
}   

void change(){
    int nf=2;
    for (int i=n+m+1;i!=0;i=g[fa[i]].x)
      if (g[fa[i]].c    flow+=nf;
    for (int i=n+m+1;i!=0;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }   
}   

void sap(){
    num[0]=n+m+2;
    for (int i=0;i<=n+m+1;i++) cur[i]=ls[i];
    int i=0;
    while (d[0]        while (cur[i]!=0){
            if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
            cur[i]=g[cur[i]].next;
        }
        if (cur[i]==0){
            num[d[i]]–;
            if (num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=0) i=g[fa[i]].x;
        }   
        else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==n+m+1){
                change();
                i=0;
            }   
        }   
    }
}   

void addlist(int key,int pos){
    list[pos][++list[pos][0]]=key;
}   

void print(){
    if (flow        printf("NOn");
        return;
    }   
    printf("YESn");
    for (int i=1;i      if (g[i].x==0 && g[i].c==0){
          int t=ls[g[i].y];
          while (t!=0){
              if (g[t].y>=n+1 && g[t].y<=n+m && g[t].c==0){
                  addlist(g[i].y,g[t].y-n);
                  break;
              }   
              t=g[t].next;
          }   
      }   
    for (int i=1;i<=m;i++)
        printf("2 %d %dn",list[i][1],list[i][2]);
}   

int main(){
    init();
    sap();
    print();
    return 0;
}   

[POJ 2763] 树状数组 LCA RMQ

题意:

给定一棵无根树(边无向),你一开始在s点上。

每次有两种操作。

1、0 x

表示走到x点上

2、1 i w

将第i条边的权值变为w

分析:

首先如果定义一个根,且d[i]为i点到根的距离。

那么必有dis(i,j)=d[i]+d[j]-2*d[lca(i,j)]

先按dfs顺序把点放进一个队列,这样如果以某点为根的子树的结点就会连续排列

这样如果把某一条边改变以后,就相当如把以深度较大的那个点的为根的子树的所有d值都变为那个值。

那么这样的话就可以用线段树或者树状数组实现了。

插曲:

WA了很多遍,一开始work里很多东西写错,后来发现LCA写错。

cai0715-problem-solutions数据结构部分正式结束。

code:

#include #include #define N 222222
struct gtp{int x,y,w,next;}g[N];
int n,q,cur,ls[N],e,dep[N],d[N];
int Ql[N],Qt=0,pl[N],pr[N],El[N],Et=0,R[N],log2[N];

struct rmqtype{
    int w[20][N],who[20][N];
    void build(){
        int maxk=log2[Et];
        for (int i=1;i<=Et;i++) {
            w[0][i]=dep[El[i]];
            who[0][i]=El[i];
        }
        for (int k=1;k<=maxk;k++){
            int t=1<            for (int i=1;i+(1<              if (w[k-1][i]                  w[k][i]=w[k-1][i];
                  who[k][i]=who[k-1][i];
              }
              else{
                  w[k][i]=w[k-1][i+t];
                  who[k][i]=who[k-1][i+t];
              }
        }
    }
    int lca(int l,int r){
        int t;
        if (r        t=log2[r-l+1];
        if (w[t][l]        return who[t][r-(1<    }
}rmq;

struct Tree_Array_Type{
    int a[N];
    void clear(){memset(a,0,sizeof(a));}
    void add(int pos,int x){
        for (int i=pos;i<=n;i+=(i & -i)) a[i]+=x;
    }
    int sum(int pos){
        int t=0;
        for (int i=pos;i>=1;i-=(i & -i)) t+=a[i];
        return t;
    }
}Tarr;

void addedge(int x,int y,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}

void init(){
    memset(ls,0,sizeof(ls));
    memset(dep,0,sizeof(dep));
    int pre=-1;
    for (int i=1;i<=N;i++)
      if ((1<<(pre+1))==i) log2[i]=++pre;
                      else log2[i]=pre;
    scanf("%d%d%d",&n,&q,&cur);
    for (int i=1;i<=n-1;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        addedge(x,y,w);
        addedge(y,x,w);
    }
}

void predfs(int p,int nowdep,int distance){
    El[++Et]=p;
    R[p]=Et;
    Ql[++Qt]=p;
    dep[p]=nowdep;
    pl[p]=Qt;
    d[p]=distance;
    for (int t=ls[p];t>0;t=g[t].next)
      if (dep[g[t].y]==0) {
          predfs(g[t].y,nowdep+1,distance+g[t].w);
          El[++Et]=p;
      }
    pr[p]=Qt;
}

void Build(){
    Tarr.clear();
    for (int i=1;i<=n;i++) {
        Tarr.add(pl[i],d[i]);
        Tarr.add(pl[i]+1,-d[i]);
    }
    rmq.build();
}

void work(){
    int op,x,y;
    for (int k=1;k<=q;k++){
        scanf("%d",&op);
        if (op==0){
           scanf("%d",&x);
           int fa=rmq.lca(R[cur],R[x]);
           printf("%dn",Tarr.sum(pl[cur])+Tarr.sum(pl[x])-2*Tarr.sum(pl[fa]));
           cur=x;
        }
        else{
            scanf("%d%d",&x,&y);
            int p=g[x*2].x;
            if (dep[g[x*2].x]            int change=y-g[x*2].w;
            Tarr.add(pl[p],change);
            Tarr.add(pr[p]+1,-change);
            g[x*2-1].w=y;
            g[x*2].w=y;
        }
    }
}

int main(){
    init();
    predfs(1,1,0);
    rmq.build();
    Build();
    work();
    return 0;
}

SGU155 笛卡尔树

题意:

给定N个二元组(Ki,Ai)

让你建立一棵笛卡尔树。

这个笛卡尔树实际上就是一个Treap.

k为二叉排序树的关键字,a为堆的关键字,堆是一个小根堆。

分析:

直接Treap会TLE,因为他给定了关键值,会退化成O(n^2)

然后我们可以根据Ki把结点从小到大排序,

然后每次都是最右边插入新的结点,

然后维护只需要左旋(他们叫右旋= =我觉得向左比较形象)

只有左旋的话我们可以注意到两个性质:

1、那么就是旋转以后,我这个结点不会增加新的儿子。

2、旋转以后,我必然是下一次插入的点的父结点。

别问我问什么。。。手画一下。。。证明这东西不是我这个级别做的事

然后我们可以注意到,从根开始连续向右到底这条路径可以看成一个

每次左旋,就是一次出栈操作。

每次加结点,就是一次入栈操作。

于是,加结点和左旋操作数都<=n

所以,证明了这个算法的复杂度是:O(N)!

  

HINT

1A。

code:

#include #include #define N 60000
using namespace std;
struct re{int k,a,wz;}d[N];
struct trtype{int l,r,fa,zz;}tr[N];
int n,tot,mr,locate[N];

void left(int t){
    int p=tr[t].fa;
    tr[p].r=tr[t].l;
    tr[tr[t].l].fa=p;
    tr[t].l=p;
    tr[0].l=0; tr[0].r=0; tr[0].fa=0; tr[0].zz=0;
    if (tr[tr[p].fa].l==p) tr[tr[p].fa].l=t;
    if (tr[tr[p].fa].r==p) tr[tr[p].fa].r=t;
    tr[t].fa=tr[p].fa;
    tr[p].fa=t;
}   

void work(){
    tot=1; mr=1; tr[1].l=0; tr[1].r=0; tr[1].fa=0; tr[1].zz=1;
    for (int i=2;i<=n;i++){
        tot++;
        tr[tot].l=0; tr[tot].r=0; tr[tot].zz=i; tr[tot].fa=mr; tr[mr].r=tot;
        mr=tot;
        int now=tot;
        while (tr[now].fa!=0 && d[tr[tr[now].fa].zz].a>d[i].a)
          left(now);
    }   
}   

inline int wz(int x){
    return d[tr[x].zz].wz;
}   

void print(){
    printf("YESn");
    for (int i=1;i<=tot;i++) locate[d[tr[i].zz].wz]=i;
    for (int i=1;i<=n;i++){
        int t=locate[i];
        printf("%d %d %dn",wz(tr[t].fa),wz(tr[t].l),wz(tr[t].r));
    }   
}   

bool cmp(re x,re y){
    if (x.k    return false;
}   

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&d[i].k,&d[i].a);
        d[i].wz=i;
    }
    sort(&d[1],&d[n+1],cmp);
    work();
    print();
    return 0;
}   

SPOJ 220 后缀数组 分组思想

题意:

题目:https://www.spoj.pl/problems/PHRASES/

给定N个字符串,让你求一个最长的串,使得他满足:

在每个串中它都出现过>=两次,而且出现的位置不重叠。

分析:

就是构造后缀数组,然后二分答案,用分组思想,看能否实现。

HINT

一开始没看到不能重叠,WA了一遍。

code:

#include #include #include using namespace std;
const int N=111111;
char s[N];
struct gtp{int data[3],next;}g[N];
int cn,ls[N],color[N],e,n,sa[N],rank[N],a[N][3],G[N],hash[N],num[N],height[N],maxsa[N],minsa[N],list[N];

void init(){
     char inschar=’A’,ch;
     scanf("%dn",&cn);
     n=0;
     for (int i=1;i<=cn;i++){
         while (scanf("%c",&ch)!=EOF && ch!=’n’)
           if (ch>=’a’ && ch<='z'){
             s[++n]=ch;
             color[n]=i;
           }
         s[++n]=inschar++;
         color[n]=0;
     }
}

inline bool cmp(int x,int y){
     if (s[x]     return false;
}

inline void add(int x,int data[]){
       e++;
       g[e].next=ls[x]; ls[x]=e;
       memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
     for (int k=1;k>=0;k–){
         e=0;
         memset(ls,0,sizeof(int)*(n+1));
         for (int i=n;i>=1;i–) add(a[i][k],a[i]);
         int tail=0;
         for (int i=0;i<=n;i++)
           for (int t=ls[i];t!=0;t=g[t].next)
             memcpy(a[++tail],g[t].data,sizeof(a[0]));
     }
}

void buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     sort(&sa[1],&sa[n+1],cmp);
     int tail=0;
     for (int i=1;i<=n;i++){
         if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
         rank[sa[i]]=tail;
     }
     for (int k=1;1<         int t=1<         for (int i=1;i<=n;i++){
             a[i][0]=rank[i];
             if (i+t<=n) a[i][1]=rank[i+t];
                    else a[i][1]=0;
             a[i][2]=i;
         }
         Jsort();
         tail=0;
         for (int i=1;i<=n;i++){
             if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
             rank[a[i][2]]=tail;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void MakeHeight(){
     memset(height,0,sizeof(int)*(n+1));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]) {j++;k++;st++;}
         height[rank[i]]=st;
     }
}

bool flag(int limit){
     int Gn=1; G[1]=1;
     for (int i=2;i<=n;i++)
       if (height[i]>=limit) G[i]=Gn;
                        else G[i]=++Gn;
     int j=1;
     for (int i=1;i<=Gn;i++){
         int st=j,total=0,tail=0;
         while (j<=n && G[j]==i) j++;
         for (int k=st;k           if (hash[color[sa[k]]]!=i){
             hash[color[sa[k]]]=i;
             num[color[sa[k]]]=1;
             minsa[color[sa[k]]]=sa[k];
             maxsa[color[sa[k]]]=sa[k];
             list[++tail]=color[sa[k]];
           }
           else{
             num[color[sa[k]]]++;
             minsa[color[sa[k]]]=min(minsa[color[sa[k]]],sa[k]);
             maxsa[color[sa[k]]]=max(maxsa[color[sa[k]]],sa[k]);
             if (num[color[sa[k]]]==2 && color[sa[k]]!=0) total++;
           }
         if (total!=cn) continue;
         bool ff=true;
         for (int k=1;k<=tail;k++)
           if (maxsa[k]-minsa[k]         if (ff) return true;
     }
     return false;
}

void binary(){
     int l=0,r=n,mid;
     while (l+1           mid=l+r>>1;
           if (flag(mid)) l=mid;
                     else r=mid-1;
     }
     if (flag(r)) printf("%dn",r);
             else printf("%dn",l);
}

int main(){
    int testcase;
    scanf("%d",&testcase);
    for (int i=1;i<=testcase;i++){
        init();
        buildarr();
        MakeHeight();
        binary();
    }
}