對酒當歌,人生幾何? 譬如朝露,去日苦多

admin 发布的文章

优质博客推荐

hdu6115

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int inf=0x3f3f3f3f;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=100005;
int n,m;
int vis[maxn];
int deep[maxn];
int dis[maxn];
int p[maxn][25];
vector<int>v1[maxn];
int tot;
struct node
{
    int u,v,w,nex;
} e[maxn*10];
int first[maxn];

void edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void init()
{
    tot=0;
    mem(first,-1);
    mem(vis,0);
    mem(dis,0);
    mem(deep,0);
    mem(p,0);
    for(int i=0; i<=n; i++)
        v1[i].clear();
}
void dfs(int u,int d,int pre)
{
    vis[u]=1;
    dis[u]=d;
    for(int i=1; i<=22; i++)
    {
        p[u][i]=p[p[u][i-1]][i-1];
    }
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        int v=e[i].v;
        if(pre==v) continue;
        if(!vis[v])
        {
            deep[v]=deep[u]+1;
            p[v][0]=u;
            dfs(v,d+e[i].w,u);
        }
    }
}
int LCA(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=22; i>=0; i--)
    {
        if(deep[y]<=deep[p[x][i]])
        {
            x=p[x][i];
        }
    }
    if(x==y) return x;
    for(int i=22; i>=0; i--)
    {
        if(p[x][i]!=p[y][i])
        {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        int u,v,w;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge(u,v,w);
            edge(v,u,w);
        }
        for(int i=1; i<=m; i++)
        {
            int p;
            scanf("%d",&p);
            for(int j=1; j<=p; j++)
            {
                int aa;
                scanf("%d",&aa);
                v1[i].push_back(aa);
            }
        }
        dfs(1,0,-1);
        int q;
        scanf("%d",&q);
        for(int i=1; i<=q; i++)
        {
            int minn=inf;
            scanf("%d%d",&u,&v);
            for(int j=0; j<v1[u].size(); j++)
            {
                for(int k=0; k<v1[v].size(); k++)
                {
                    int uu=v1[u][j];
                    int vv=v1[v][k];
                    int gg=LCA(uu,vv);
                    //printf("gg=%d\n",gg);
                    minn=min(minn,dis[uu]+dis[vv]-2*dis[gg]);
                }
            }
            printf("%d\n",minn);
        }
    }
    return 0;
}

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ofstream file;
    file.open("yuyin.txt");
    string s;
    char bd='"';
    while(cin>>s)
    {
        if(s[0]==s[1]&&s[1]=='0') break;
        int len=s.size();
        for(int i=0;i<len;i++)
        {
            if(s[i]=='"')
                s[i]='.';
        }
        char bd='"';
        file<<"CreateObject(";
        file<<bd;
        file<<"SAPI.SpVoice";
        file<<bd;
        file<<").Speak";
        file<<bd;
        file<<s;
        file<<bd;
        file<<"\n";
    }

}

 

LCA就是求公共祖先。优质博客推荐
但是不推荐它的伪代码,感觉思路没错,但是有点问题。
我随手写了一个,有错欢迎之处

int get(int u)
{
    if(f[u]==u) return u;
    else f[u]=get(f[u]);
}
void dfs(int u,int pre)
{
    //vis[u]=1;//位置1
    for(int i=first[u];i!=-1;i=e[i].nex)
    {
        int v=e[i].v;
        if(pre==v) continue;
        if(!vis[v])
        {
            dfs(v,u);
            f[v]=u;
        }
    }
    vis[u]=1;//位置2
    for(int i=first2[u];i!=-1;i=e2[i].nex)
    {
        int v=e2[i].v;
        int id=e2[i].id;
        if(!vis[v])
        {
            ans[id]=get(v);
        }
    }
}

vis[u]为什么放哪个地方而不放在f[v]=u前面,因为那样遍历不到根节点。
无向图可以放在位置1和位置2,讲道理,位置1更快。
但是有向图只能放在位置2,否则提前标记自己,但是自己不一定是祖先,因为自己是有向图。

那么公共祖先有什么用呢?
裸题有用,但是大部分都不是,我学了一个求两点间距离,有意思的很。
首先说一下无向图,只需在dfs的时候传递一个deep变量一直逐层加就好了。
然后dis[u]=deep,那么就两点间距离就是dis[u]+dis[v]-2*dis[get(v)]。
那么有向图必需从根节点dfs,无向图可以从任意节点。

无向图求两点距离

hdu2874

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int maxn=20005;
const int maxm=2000005;
int n,m,c;

struct node
{
    int v,w,nex;
} e[maxn];
struct node2
{
    int id,v,nex;
} e2[maxm];
int first[maxn/2];
int first2[maxn/2];
int tot,tot2;

int vis[maxn];
int f[maxn];
int dis[maxn];
int ans[maxm/2];
void edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void edge2(int id,int u,int v)
{
    e2[tot2].id=id;
    e2[tot2].v=v;
    e2[tot2].nex=first2[u];
    first2[u]=tot2++;
}
void init()
{
    mem(first,-1);
    mem(first2,-1);
    tot=0;
    tot2=0;
    mem(vis,0);
    for(int i=1; i<=n; i++)
    {
        f[i]=i;
    }
    mem(dis,0);
    mem(ans,-1);
}
int get(int u)
{
    if(f[u]==u)
    {
        return u;
    }
    else
    {
        return f[u]=get(f[u]);
    }
}
//void marge(int u,int v)
//{
//    int f1=get(u);
//    int f2=get(v);
//    if(f1!=f2)
//        f[f2]=f1;
//}
int dfs(int u,int pre,int deep,int root)
{
    vis[u]=root;
    dis[u]=deep;
    int v;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        v=e[i].v;
        if(v==pre) continue;
        //printf("%d %d\n",u,v);
        if(!vis[v])
        {
            //printf("       %d\n",v);
            dfs(v,u,deep+e[i].w,root);
            f[v]=u;
        }
    }
    for(int i=first2[u]; i!=-1; i=e2[i].nex)
    {
        v=e2[i].v;
        if(vis[v]==root)
        {
            //printf("           %d %d %d\n",dis[u],dis[v],get(v));
            ans[e2[i].id]=dis[u]+dis[v]-2*dis[get(v)];
        }
    }
}
void LCA()
{
    for(int i=1; i<=n; i++)
    {
        //printf("i=%d\n",i);
        if(!vis[i])
        {
            //printf("i=%d\n",i);
            dfs(i,-1,0,i);
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&c))
    {
        init();
        for(int i=0; i<m; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            edge(u,v,w);
            edge(v,u,w);
        }
        for(int i=1; i<=c; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            edge2(i,u,v);
            edge2(i,v,u);
        }
        LCA();
        for(int i=1; i<=c; i++)
        {
            if(ans[i]!=-1)
                printf("%d\n",ans[i]);
            else
                printf("Not connected\n");
        }
    }
    return 0;
}

有向图两点间距离

hdu2586

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=40010;
int n,m;
int vis[maxn];
int f[maxn];
//int pre[maxn];
int ans[maxn];
int dis[maxn];
map<string,int>str;
int top;

int tot,tot2;
struct node
{
    int u,v,w,nex;
} e[maxn*10];
int first[maxn];

struct node2
{
    int id;
    int u,v,nex;
} e2[maxn*10];
int first2[maxn];

void edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void edge2(int id,int u,int v)
{
    e2[tot2].id=id;
    e2[tot2].u=u;
    e2[tot2].v=v;
    e2[tot2].nex=first2[u];
    first2[u]=tot2++;
}

void init()
{
    tot=tot2=0;
    mem(first,-1);
    mem(first2,-1);
    mem(vis,0);
    for(int i=0; i<=n; i++)
    {
        f[i]=i;
    }
    mem(ans,0);
    top=0;
    //mem(pre,-1);
}
int get(int u)
{
    if(f[u]==u)
        return u;
    else
        return f[u]=get(f[u]);
}
void dfs(int u,int deep,int pre)
{
    vis[u]=1;
    dis[u]=deep;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        int v=e[i].v;
        if(pre==v) continue;
        if(!vis[v])
        {
            dfs(v,deep+e[i].w,u);
            f[v]=u;
        }
    }
    for(int i=first2[u]; i!=-1; i=e2[i].nex)
    {
        int v=e2[i].v;
        int id=e2[i].id;

        if(vis[v])
        {
            ans[id]=dis[u]+dis[v]-2*dis[get(v)];
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        int u,v,w;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge(u,v,w);
            edge(v,u,w);
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            edge2(i,u,v);
            edge2(i,v,u);
        }
        dfs(1,0,-1);
        for(int i=1; i<=m; i++)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}

 

这里有几个点需要注意
1.为什么无向图缩点需要变成有向图缩点?
无向图两两之间的点可以到达,无法跑回边的话,就跑不到父节点以上的节点了,那么肯定是桥了。
2.为什么不能跑回边,而不是跑父节点?
本来是个无向图单连通,但是你阻止了父节点跑回去,那就不是无向图单连通了。
但是这个题去重也对,嗯。。。数据弱

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int maxn=10005;

struct node
{
    int u,v,nex;
} e[maxn*maxn];
int first[maxn];
int tot;
int n,m;
int ans,din,top;
int dfn[maxn],low[maxn],Stack[maxn],in[maxn];
int belong[maxn];
void init()
{
    mem(first,-1);
    tot=0;
    din=1;
    ans=0;
    top=0;
    mem(dfn,0);
    mem(low,0);
    mem(Stack,0);
    mem(in,0);
    mem(belong,0);
}
void edge(int u,int v)
{
    e[tot].u=u;
    e[tot].v=v;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void tarjan(int u,int id)
{
    dfn[u]=low[u]=++din;
    Stack[top++]=u;
    in[u]=1;
    int v;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        v=e[i].v;
        if(i==(id^1))
            continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
        {
            low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        ans++;
        do
        {
            v=Stack[--top];
            in[v]=0;
            belong[v]=ans;
            //printf("%d\n",ans);
        }
        while(v!=u);
    }
}
void scc()
{
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i])
            tarjan(i,-1);
    }
    //printf("%d\n",ans);
    int sum=0;
    int k=0;
    int aa[maxn],gg[maxn];
    mem(aa,0);
    mem(gg,0);
    for(int i=0; i<tot; i+=2)
    {
        int u=e[i].u;
        int v=e[i].v;
        if(belong[u]!=belong[v])
        {
            //printf("%d %d\n",belong[u],belong[v]);
            aa[belong[u]]++;
            aa[belong[v]]++;
        }
    }
    for(int i=1; i<=ans; i++)
    {
        if(aa[i]==1) sum++;
    }
    printf("%d\n",(sum+1)/2);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
//            int flag=0;
//            for(int j=first[u]; j!=-1; j=e[j].nex)
//            {
//                int to=e[j].v;
//                if(v==to)
//                {
//                    flag=1;
//                    break;
//                }
//            }
//            if(flag==1) continue;
            edge(u,v);
            edge(v,u);
        }
        scc();
    }
}

 

博客推荐

与割点的最大不同之处:low[v]>low[u]

易错点:

1.父亲节点与子节点区别一下,防止两个点误认为环。

2.去重边

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int maxn=10005;
int n,m;
struct node2
{
    int x,y;
} ee[maxn*maxn];
int cmp(node2 a,node2 b)
{
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}
struct node
{
    int v,nex;
} e[maxn*maxn];
int first[maxn];
int tot,top,ans,din,cnt;
int dfn[maxn],low[maxn],Stack[maxn],in[maxn];
int son,flag[maxn];
void init()
{
    mem(first,-1);
    tot=0;
    top=0;
    din=0;
    son=0;
    ans=0;
    cnt=0;
    mem(dfn,0);
    mem(low,0);
    mem(Stack,0);
    mem(in,0);
    mem(flag,0);
}
void edge(int u,int v)
{
    e[tot].v=v;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void tarjan(int u,int vv)
{
    dfn[u]=low[u]=++din;
    Stack[top++]=u;
    in[u]=1;
    int v;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {

        v=e[i].v;
        if(i==(vv^1)) continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            //printf("       %d %d\n",low[v],dfn[u]);
            if(low[v]>dfn[u])
            {
                ee[cnt].x=v;
                ee[cnt].y=u;
                if(v>u)
                    swap(ee[cnt].x,ee[cnt].y);
                cnt++;
            }
        }
        else if(in[v]&&low[u]>dfn[v])
        {
            //printf("       %d %d\n",u,v);
            low[u]=dfn[v];
        }
    }//printf("sdfa\n");
}

int main()
{
    int tt=1;
    while(~scanf("%d",&n))
    {
        if(n==0)
        {
            printf("0 critical links\n\n");
            continue;
        }
        init();
        int u,v,k;
        for(int i=0; i<n; i++)
        {
            scanf("%d (%d)",&u,&k);
            for(int j=0; j<k; j++)
            {
                scanf("%d",&v);
                int flag=0;
                for(int j=first[u]; j!=-1; j=e[j].nex)
                {
                    int qq=e[j].v;
                    if(qq==v)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==1) continue;
                //printf("%d %d\n",u,v);
                edge(u,v);
                edge(v,u);
            }
        }
        for(int i=0; i<n; i++)
        {
            if(!dfn[i])
                tarjan(i,-1);
        }
        sort(ee,ee+cnt,cmp);
        printf("%d critical links\n",cnt);
        for(int i=0; i<cnt; i++)
        {
            printf("%d - %d\n",ee[i].x,ee[i].y);
        }
        printf("\n");
    }
    return 0;
}