edward_mj

[POJ1741 Tree]基于点划分的树的分治算法、男人8题

【题目大意】

给出一棵树，让你求树中距离<=K的点对个数。

【算法分析】

围观了一下漆子超大神的论文。。。表示那实在太简略了。。。我只能从中得到一些启发。

首先是按他说的那样，对树进行基于点的划分。

划分的方法是：每次对当前块选一个根，使得去掉这个点以后，划分出新的各个块中点数最多的最少。

这个利用DFS搜一下，维护一个表示以该节点为根的子树的点数多少的数组size[i]。然后当前这个点当分割点，分成各个块的大小就可以很容易算出来。

划分好以后，就从划分树的底层向顶层扫描（其实这个顺序只要是拓扑序就可以了）。

扫描上去的过程中，将划分树当前区间的点都放进一个队列里面，并将它们按到“划分点”的距离排个序。

然后用j从前面开始扫描，并维护另一个指针k，指向一个点满足k=max(k : dis[Q[k]]+dis[Q[j]]<=K)。

接着再减去那些与当前点在下一层里属于同一个划分区间的点的数量，就是经过该根并满足<=K的路径的数量。把它们全加起来就是ans。

【其他】

写了个朴素对拍调试才A。。。之前因为维护k指针的时候k–写在那个if前面了，所以搞错了。。。

终于成为了1/2个男人

【CODE】

#include #include #include #include #include #include using namespace std;
const int E=333333;
const int N=122222;
const int INF=1000000000;
struct edge{int x,y,w;edge *next;}g[E],*ls[N];
struct linetreetype{int l,r,dep,root;}tr[N*16];
int n,K,e,Qt,NowDep,ans;
int color[16][N],list[16][N],tot[16],dis[N],size[N];
int Q[N],use[N],done[N];

struct LineTreeFunction{
int times,nowroot,nownum,trtot;

       void makelabel(int p,int *co,int fa){
            size[p]=times++;
            for (edge *t=ls[p];t;t=t->next)
              if (co[t->y]==co[p] && t->y!=fa){
                dis[t->y]=dis[p]+t->w;
                makelabel(t->y,co,p);
              }
            size[p]=times-size[p];
       }

       void choose_root(int p,int *co,int fa,int total){
           int now=0;
           if (fa) now=max(now,total-size[p]);
           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               now=max(now,size[t->y]);
           if (now           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               choose_root(t->y,co,p,total);
       }

       void buildnewlp(int p,int fa,int *co,int dep){
           list[dep][++tot[dep]]=p;
           for (edge *t=ls[p];t;t=t->next)
             if (co[t->y]==co[p] && t->y!=fa)
               buildnewlp(t->y,p,co,dep);
       }

       void build(int p,int l,int r,int dep){
            tr[p].l=l; tr[p].r=r; tr[p].dep=dep;
            int &st=list[dep][l];
            for (int i=l;i<=r;i++) color[dep][list[dep][i]]=p;
            if (l==r) return;
            dis[st]=0; times=0; nownum=INF;
            makelabel(st,color[dep],0);
            choose_root(st,color[dep],0,r-l+1);
            tr[p].root=nowroot;

            for (edge *t=ls[tr[p].root];t;t=t->next)
              if (color[dep][t->y]==p){
                int pt=tot[dep+1]+1,nt;
                buildnewlp(t->y,tr[p].root,color[dep],dep+1);
                nt=tot[dep+1];
                trtot++;
                build(trtot,pt,nt,dep+1);
              }
       }
}LineTree;

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

void init(){
     e=0;
     for (int i=1;i<=n;i++) ls[i]=NULL;
     memset(color,0,sizeof(color));
     memset(list,0,sizeof(list));
     memset(tot,0,sizeof(tot));
     for (int i=1;i         int x,y,w;
         scanf("%d%d%d",&x,&y,&w);
         addedge(x,y,w);
         addedge(y,x,w);
     }
     tot[1]=n;
     for (int i=1;i<=n;i++) list[1][i]=i;
}

bool cmp(int x,int y){
return (dis[x])<(dis[y]);
}

void work(){
    ans=0;
    memset(use,0,sizeof(use));
    memset(done,0,sizeof(done));
    for (int i=LineTree.trtot;i>=1;i–){
        if (tr[i].l==tr[i].r) continue;
        dis[tr[i].root]=0;
        LineTree.times=0;
        LineTree.makelabel(tr[i].root,color[tr[i].dep],0);
        NowDep=tr[i].dep+1;
        Qt=0;
        int j,k=0;
        for (j=tr[i].l;j<=tr[i].r;j++)
          Q[++Qt]=list[tr[i].dep][j];
        sort(Q+1,Q+Qt+1,cmp);
        int *co=color[tr[i].dep+1];
        for (j=1;j<=Qt;j++){
          if (co[Q[j]] && use[co[Q[j]]]!=i){
              use[co[Q[j]]]=i;
              done[co[Q[j]]]=0;
          }
          while (k+1            k++;
            if (co[Q[k]])
              done[co[Q[k]]]++;
          }
          while (k>0 && dis[Q[j]]+dis[Q[k]]>K){
            if (co[Q[k]])
              done[co[Q[k]]]–;
            k–;
          }
          ans+=k-done[co[Q[j]]];
        }
    }
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for (;;){
        scanf("%d%d",&n,&K);
        if (!n && !K) break;
        init();
        LineTree.trtot=1;
        LineTree.build(1,1,n,1);
        work();
        cout << ans << endl;
    }
}

[NOI2007 day1 社交网络]floyed变形

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1491

【算法分析】

就是利用floyed求最短路。然后加多一个数组表示num[i][j]表示从i到j的最短路的数目。

然后在松弛的地方因为乘法原理，应当变成num[i][k]*num[k][j]，相等的话要加上方案。

最后统计一下就好了。

【其它】1A

【CODE】

#include using namespace std;
int n,m;
int d[122][122];
long long num[122][122];

void input(){
    memset(d,50,sizeof(d));
    memset(num,0,sizeof(num));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        d[x][y]=w;
        d[y][x]=w;
        num[x][y]=1;
        num[y][x]=1;
    }
}

void floyed(){
    int i,j,k;
    for (k=1;k<=n;k++)
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if (i!=j && j!=k && i!=k){
              if (d[i][k]+d[k][j]                  d[i][j]=d[i][k]+d[k][j];
                  num[i][j]=num[i][k]*num[k][j];
              }
              else if (d[i][k]+d[k][j]==d[i][j])
                  num[i][j]+=num[i][k]*num[k][j];
          }
}

void output(){
    int i,j,k;
    for (k=1;k<=n;k++){
        double ans=0;
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
            if (i!=j && j!=k && i!=k && d[i][j]==d[i][k]+d[k][j])
                ans+=num[i][k]*num[k][j]*1.0/num[i][j];
        printf("%.3lfn",ans);
    }
}

int main(){
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    input();
    floyed();
    output();
}

[HDOJ3374 String Problem]字符串循环的最小表示

【题目大意】

寻找最小字典序循环串起始位置，和最大字典序循环串起始位置

并分别输出这个串在循环中所出现的次数。

【算法分析】

利用经典算法求出他们最小表示的位置。然后用KMP算出现了几次。

【其它】

1A。

好像挺慢的。。。

【CODE】

#include #include

char s[2001111],p[1001111];
int next[1001111],n;

int minshow(){
    int i=1,j=2,k=0;
    while (i<=n && j<=n && k<=n){
        if (s[i+k]==s[j+k]) k++;
        else{
            if (s[i+k]>s[j+k]) i+=k+1;
                          else j+=k+1;
            if (i==j) i++;
            k=0;
        }
    }
    return i}

int maxshow(){
    int i=1,j=2,k=0;
    while (i<=n && j<=n && k<=n){
        if (s[i+k]==s[j+k]) k++;
        else{
            if (s[i+k]>s[j+k]) j+=k+1;
                          else i+=k+1;
            if (i==j) i++;
            k=0;
        }
    }
    return i}

void kmp(int st){
    int i,j,ans=0;
    for (i=st,j=1;j<=n;i++,j++) p[j]=s[i];

    next[1]=0; j=0;
    for (i=2;i<=n;i++){
        while (j && p[j+1]!=p[i]) j=next[j];
        if (p[j+1]==p[i]) j++;
        next[i]=j;
    }

    j=0;
    for (i=1;i<=n+n-1;i++){
        while (j && p[j+1]!=s[i]) j=next[j];
        if (p[j+1]==s[i]) j++;
        if (j==n){
            ans++;
            j=next[j];
        }
    }
    printf("%d %d",st,ans);
}

int main(){
    while (scanf("%s",s+1)!=EOF){
        n=strlen(s+1);
        memcpy(s+n+1,s+1,sizeof(char)*n);
        kmp(minshow()); printf(" ");
        kmp(maxshow()); printf("n");
    }
}

[POJ1509 Glass Beads]字符串循环的最小表示、例题

【题目大意】

寻找最小字典序循环串起始位置

【算法分析】

围观了周源的论文。还是不懂，于是又来围观了某牛的blog，知道怎样做，但是感觉不能保证正确？

【CODE】

#include #include #include #include using namespace std;
int n;
char s[33333];

int minishow(){
int i=1,j=2,k=0;
while (i<=n && j<=n && k<=n){
if (s[i+k]==s[j+k]) k++;
else{
if (s[i+k]>s[j+k]) i+=k+1;
else j+=k+1;
if (i==j) i++;
k=0;
}
}
return min(i,j);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=0;iscanf("%s",s+1);
n=strlen(s+1);
for (int j=n+1;j<=n*2;j++) s[j]=s[j-n];
cout << minishow() << endl;
}
}