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

分类 ACM算法 下的文章

第一步
开始学习二分图需掌握。
1.增广路径是什么?
其实二分图就是找增广路径,每找到一条增广路径,ans++。所以要弄清增广路径是什么。
2.掌握匈牙利算法。
匈牙利算法就是找增广路径的,所以掌握后就算真正学会二分图。


困惑:
1.无向二分图?有向二分图?
无向二分图:
比如u跟v是增广路,由于每个点都跑了一次,那么u-v和v-u都找了一次,那么无向二分图最后找的是最大匹配点。
有向二分图:
如果有这样三个点,a到b,b到c。那么找的时候肯定会找两次,最后是match[b]=a,match[c]=b。所以相当于找了一条路(a->b->c)上边数。


第二步
二分图最小路径覆盖
目的:找出最少路径数覆盖所有点。(什么样的路径由题目定义)
无向图:单纯的找出最少路径数覆盖所有点的话。
结论:ans=n-二分图最大匹配/2。
想一下无向图最大二分图匹配找出了最多匹配了多少点,那覆盖这些点只需(二分图最大匹配/2)个点,其他点都需要一条边,所以是其他点需要(n-二分图最大匹配)个点,相加得出结果。

有向图:如果一个士兵在u点,他能顺路一直走下去,但不能回走,问需要多少个这样的士兵。
结论:ans=n-二分图最大匹配。
前面已经说过了,有向二分图相当与找到一条路径上的边数,那么找到问题所问的点就很简单了,n-二分图最大匹配。
第三步
二分图最小点覆盖数
目的:选取最少的点,使任意一条边至少有一个端点被选择,图应该形成一个树。
结论:ans=二分图最大匹配。
二分图最大匹配完以后肯定都是由增广路径得来的,那么由增广路径的定义我们可以想到。
~9)@H$}NBL$YM(@$`S32~~J.png

优质博客推荐

问题描述:母串S,子串T,求S[i]~S[n-1] (0<=i<n) ,与T的最长公共前缀extend[i]。

求解需要next数组辅助,next[i]表示next[i]~next[m-1]与next[0]~next[m-1]的最长公共前缀。

我们直接讨论在中间时匹配的情况。

已知:

1.假如我们extend已经求到了k,该求k+1了。

2.位置p代表extend[0,k]能匹配到的最远的位置,并且设取这个最大值的位置为po。

3.next数组已知,next[k+1]=len。

求extend数组

一。k+len<p

如上图

此时extend[k+1]=next[k+1]=len;

S[k+len+1]不会等于T[len],如果它们相等,那么就表示T[k+len-1-po]==T[len],那么next[k+1]=len+1,冲突,那么错误。

二。k+len>=p

因为我们最远才匹配到p,所以S[p+1]以后的字符和T[p-k]以后的字符一一开始匹配,直到失配为止。

如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。

然后求extend就结束了,而求next数组就和extend一样了,只不过把母串换了换。

 

优质博客推荐

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;
}