day 6：图论（上）

叁歲伎倆 2021-10-30 06:12 230阅读 0赞

# day 6：图论（上） #

今天讲的还是挺简单的，但是还是对Prim算法不熟练，这应该是要闭着眼都得会的模板啊…

然后，在求最短路径时，如果存在负权时：**Dijkstra算法**将不再适用，于是就引进了**Bellman-Ford算法**，还有它的优化版**SPFA算法**，后两者本打算晚上补的，但是又由于某些原因导致现在就11点多了，估计又不知道得拖到什么时候补了

虽然上午后面讲的那个Bellman-Ford算法，完全没听懂，但是下午的练习题却没有涉及到这个算法，全是一些比较基础的题，但是还是没有在三个小时内AK，tcl…

A题：[poj 1251：Jungle Roads][poj 1251_Jungle Roads]

开始没看这道题，虽然知道应该不会太难，但是看着这题目我就有点醉了，等A了E题之后，看着好多人都A了这道题，于是就看了下题，其实也就是一个简单的**最小生成树**题，用**Prim算法**和**Kruskal算法**都能实现，但由于我Prim算法，感觉还是学的不好，于是就用Prim算法写的

可能这稍微复杂点的就是它的顶点是字母不是数字，于是我就预处理了一个map，用来表示字母与数字的一一对应关系

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<map>
    #include<iostream>
    using namespace std;
    const int MaxNum=0xffffff0;
    int mp[50][50];
    int cost[50];
    int vis[50];
    int n;
    void init()
    {
        
        for(int i=1;i<=n;i++)
        {
        
            for(int j=1;j<=n;j++)
            {
        
                if(j==i)
                    mp[i][j]=0;
                else
                    mp[i][j]=MaxNum;
            }
        }
    }
    void Prim()
    {
        
        memset(vis,0,sizeof(vis));
        for(int i=2;i<=n;i++)
        {
        
            cost[i]=mp[1][i];
        }
        int pos;
        for(int i=1;i<=n;i++)
        {
        
            int Min=MaxNum+1;
            for(int j=1;j<=n;j++)
            {
        
                if(vis[j]==0&&Min>cost[j])
                {
        
                    Min=cost[j];
                    pos=j;
                }
            }
            vis[pos]=1;
            for(int j=1;j<=n;j++)
            {
        
                if(cost[j]>mp[pos][j]&&vis[j]==0)
                {
        
                    cost[j]=mp[pos][j];
                }
            }
        }
    }
    int main()
    {
        
        map<char,int>MAP;
        char ch='A';
        for(int i=1;i<=26;i++)
        {
        
            MAP[ch++]=i;
        }
        int m;
        int num;
        while(~scanf("%d",&n))
        {
        
            if(n==0)
                break;
            init();
            for(int i=1;i<n;i++)
            {
        
                getchar();
                scanf("%c",&ch);
                getchar();
                scanf("%d",&m);
                for(int j=0;j<m;j++)
                {
        
                    getchar();
                    scanf("%c",&ch);
                    getchar();
                    scanf("%d",&num);
                    if(mp[i][MAP[ch]]>num)
                    {
        
                        mp[i][MAP[ch]]=mp[MAP[ch]][i]=num;
                    }
                }
            }
            Prim();
            int sum=0;
            for(int i=1;i<=n;i++)
                sum+=cost[i];
            printf("%d\n",sum);
        }
        return 0;
    }

B题：[hdu 1272：小希的迷宫][hdu 1272]

很遗憾，开始没做出来，后面最后一题就是做的它，一看就是一道**无向图判环**的题，上次院赛就有一道无向图判环的题没A，这次又是…

关键后面都想到了

但是它坑的是，可能一组有用数据都没有，而此时应该输出Yes

我也是无语了

无向图环可以用**DFS**或者**并查集**，显然如果用并查集肯定会比DFS简单，但是等有时间还是用DFS实现，毕竟感觉DFS掌握的还不算太好

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int maxn=100000;
    int par[maxn+10];
    int flag;
    int vis[maxn+10];
    void init()
    {
        
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=maxn;i++)
            par[i]=i;
    }
    int get_par(int a)
    {
        
        if(par[a]!=a)
            par[a]=get_par(par[a]);
        return par[a];
    }
    void Merge(int a,int b)
    {
        
        int par_a=get_par(a);
        int par_b=get_par(b);
        if(par_a!=par_b)
            par[par_b]=par_a;
        else
            flag=1;
    }
    int main()
    {
        
        int a,b;
        memset(par,0,sizeof(par));
        while(~scanf("%d%d",&a,&b))
        {
        
            flag=0;
            if(a==-1&&b==-1)
                break;
            if(a==0&&b==0)
            {
        
                printf("Yes\n");
                continue;
            }
            init();
            vis[a]=1;
            vis[b]=1;
            Merge(a,b);
            while(~scanf("%d%d",&a,&b)&&a&&b)
            {
        
                vis[a]=1;
                vis[b]=1;
                Merge(a,b);
            }
            if(flag==1)
            {
        
                printf("No\n");
                continue;
            }
            else
            {
        
                int cnt=0;
                for(int i=1;i<=maxn;i++)
                {
        
                    if(vis[i]==1&&par[i]==i)
                    {
        
                        cnt++;
                    }
                }
                if(cnt==1)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
    }

C题：[hdu 1285：确定比赛名次][hdu 1285]

这道题虽然简单，就是一个**拓扑排序**

但是它坑的地方就是：如果两个数的排名相同的话，得从小到大输出，于是在代码中注意下即可（但是我没注意…）

做完这题之后，感觉自己的DFS又稍微好了那么一点点

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    using namespace std;
    int In[510];
    vector<int>mp[510];
    int n,m;
    int vis[510];
    vector<int>ve;
    void dfs(int i)
    {
        
        ve.push_back(i);
        //cout<<i<<endl;
        vis[i]=1;
        for(int j=0;j<mp[i].size();j++)
        {
        
            if(In[mp[i][j]]>0)
                In[mp[i][j]]--;
        }
        for(int j=1;j<=n;j++)
        {
        
            if(vis[j]==0&&In[j]==0)
            {
        
                dfs(j);
            }
        }
    }
    int main()
    {
        
        int a,b;
        while(~scanf("%d%d",&n,&m))
        {
        
            ve.clear();
            memset(In,0,sizeof(In));
            memset(mp,0,sizeof(mp));
            memset(vis,0,sizeof(vis));
            for(int i=0;i<m;i++)
            {
        
                scanf("%d%d",&a,&b);
                In[b]++;
                mp[a].push_back(b);
            }
            /*for(int i=1;i<=n;i++)
            {
                for(int j=0;j<mp[i].size();j++)
                    printf("%d ",mp[i][j]);
                printf("\n");
            }*/
            /*for(int i=1;i<=n;i++)
                cout<<In[i]<<endl;*/
            for(int i=1;i<=n;i++)
            {
        
                if(In[i]==0&&vis[i]==0)
                {
        
                    dfs(i);
                }
            }
            printf("%d",ve[0]);
            for(int i=1;i<ve.size();i++)
            {
        
                printf(" %d",ve[i]);
            }
            printf("\n");
        }
        return 0;
    }

D题：[hdu 2544：最短路][hdu 2544]

感觉是一道裸的不能再裸的**最短路径**问题，直接用**Dijkstra算法**即可

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int MaxNum=0xffffff0;
    int mp[110][110];
    int vis[110];
    int dis[110];
    int n,m;
    void init()
    {
        
        for(int i=1;i<=n;i++)
        {
        
            for(int j=1;j<=n;j++)
            {
        
                if(j==i)
                    mp[i][j]=0;
                else
                    mp[i][j]=MaxNum;
            }
        }
    }
    void Dijkstra()
    {
        
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            dis[i]=mp[1][i];
        int pos;
        for(int i=1;i<=n;i++)
        {
        
            int Min=MaxNum+1;
            for(int j=1;j<=n;j++)
            {
        
                if(vis[j]==0&&Min>dis[j])
                {
        
                    Min=dis[j];
                    pos=j;
                }
            }
            vis[pos]=1;
            for(int j=1;j<=n;j++)
            {
        
                if(vis[j]==0&&dis[j]>dis[pos]+mp[pos][j])
                    dis[j]=dis[pos]+mp[pos][j];
            }
        }
    }
    int main()
    {
        
        int a,b,c;
        while(~scanf("%d%d",&n,&m))
        {
        
            if(n==0&&m==0)
                break;
            init();
            for(int i=0;i<m;i++)
            {
        
                scanf("%d%d%d",&a,&b,&c);
                if(mp[a][b]>c)
                {
        
                    mp[a][b]=mp[b][a]=c;
                }
            }
            Dijkstra();
            printf("%d\n",dis[n]);
        }
        return 0;
    }

E题：[hdu 2066：一个人的旅行][hdu 2066]

一道以前做过的题，以前虽然没做出来，但是今天还是很顺利的A了

可能稍微比D题复杂一点点的**最短路径问题**

如果把家设为0，然后相邻城市到家的距离为0，这样问题就游刃而解了

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const  int Max=0xffffff0;
    int mp[1010][1010];
    int dis[1010];
    int vis[1010];
    const int n=1010;
    void init()
    {
        
        for(int i=0;i<=n;i++)
        {
        
            for(int j=0;j<=n;j++)
            {
        
                if(j==i)
                    mp[i][j]=0;
                else
                    mp[i][j]=Max;
            }
        }
    }
    void Dijkstra()
    {
        
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            dis[i]=mp[0][i];
        int pos;
        for(int i=1;i<=n;i++)
        {
        
            int Min=Max;
            for(int j=1;j<=n;j++)
            {
        
                if(vis[j]==0&&Min>dis[j])
                {
        
                    Min=dis[j];
                    pos=j;
                }
            }
            vis[pos]=1;
            for(int j=1;j<=n;j++)
            {
        
                if(dis[pos]+mp[pos][j]<dis[j])
                {
        
                    dis[j]=dis[pos]+mp[pos][j];
                }
            }
        }
    }
    int main()
    {
        
        int t,s,d;
        int a,b,time;
        while(~scanf("%d%d%d",&t,&s,&d))
        {
        
            init();
            for(int i=0;i<t;i++)
            {
        
                scanf("%d%d%d",&a,&b,&time);
                if(mp[a][b]>time)
                {
        
                    mp[a][b]=mp[b][a]=time;
                }
            }
            for(int i=0;i<s;i++)
            {
        
                scanf("%d",&a);
                mp[0][a]=mp[a][0]=0;
            }
            Dijkstra();
            int MinTime=Max;
            int e;
            for(int i=0;i<d;i++)
            {
        
                scanf("%d",&e);
                MinTime=min(MinTime,dis[e]);
            }
            printf("%d\n",MinTime);
        }
        return 0;
    }

一定要抽时间补**Bellman-Ford算法**

[poj 1251_Jungle Roads]: http://poj.org/problem?id=1251
[hdu 1272]: http://acm.hdu.edu.cn/showproblem.php?pid=1272
[hdu 1285]: http://acm.hdu.edu.cn/showproblem.php?pid=1285
[hdu 2544]: http://acm.hdu.edu.cn/showproblem.php?pid=2544
[hdu 2066]: http://acm.hdu.edu.cn/showproblem.php?pid=2066