暑假图论练习

程序员文章站 2022-06-03 08:33:06

1.Aizu - 0189比较水的题把 2.POJ - 2139 简单对数据处理一下，变成图就行最后注意double 3.POJ - 3268 这个有个小技巧，按照一般写会超时各个点到一个点x的最短距离可以换成x到各个点的，只需把矩阵反转一下再跑一遍图论算法就可以了 4.Aizu - 224 ......

1.比较水的题把

#include<iostream>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f
using namespace std;
int map[100][100];
int dis[100];
int vis[100];
void djst(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    dis[s]=0;
    while(1)
    {
        int k=-1,minn=inf+1;
        for(int i=0;i<10;i++)
        {
            if(!vis[i]&&dis[i]<minn)
            k=i,minn=dis[i];
        }
        if(k==-1) break;
        vis[k]=1;
        for(int i=0;i<10;i++)
        dis[i]=min(dis[i],dis[k]+map[k][i]);
    }
    
}
int main()
{
    int n;
    while(cin>>n)
    {
        memset(map,inf,sizeof(map));
        if(n==0) break;
        int nn=0;
        for(int i=0;i<n;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            nn=max(nn,max(a,b));
            if(map[a][b]>c)
            map[a][b]=map[b][a]=c;
        }
        int minn=inf,tt;
        for(int i=0;i<=nn;i++)
        {
            djst(i);
            int sum=0;
            for(int i=0;i<=nn;i++)
            {
                if(dis[i]!=inf)
                sum+=dis[i];
            }
            if(minn>sum)
            {
                minn=sum;
                tt=i;
            }
        }
        cout<<tt<<" "<<minn<<endl;
    }
    
}

2. 简单对数据处理一下，变成图就行最后注意double

#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#define inf 0x3f3f3f
using namespace std;
int map[305][305];
int vis[305];
int dis[305];
int n,m;

void prim(int s)
{
    int minn,k=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;++i)
    {
        dis[i]=map[s][i];
    }
    vis[s]=1;
    for(int i=2;i<=n;++i)
    {
        minn=inf;
        for(int j=1;j<=n;++j)
        {
            if(!vis[j]&&minn>dis[j])
            {
                k=j;
                minn=dis[j];
            }
        }
        vis[k]=1;
        for(int j=1;j<=n;++j)
        {
            if(!vis[j]&&dis[j]>dis[k]+map[k][j])
                dis[j]=dis[k]+map[k][j];
        }
    }
}

int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                if(i==j) map[i][j]=0;
                else map[i][j]=map[j][i]=inf; 
                }
            }
        
        while(m--)
        {
            int a,b,c;
            int t[10002];
            cin>>a;
            for(int i=0;i<a;i++)
            {
                cin>>t[i];
            }
            for(int i=0;i<a-1;i++)
            {
                for(int j=i+1;j<a;j++)
                {
                    if(t[i]!=t[j])
                     map[t[i]][t[j]]=map[t[j]][t[i]]=1;
                }
            }
            /*
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                cout<<map[i][j]<<" ";
                cout<<endl;
            }*/
        }
        double minn=inf;
        for(int i=1;i<=n;i++)
        {
            double sum=0;
            prim(i);
            for(int j=1;j<=n;j++)
            {
                if(i!=j)
                sum+=dis[j];
            }

            minn=minn>sum*1.0/(n-1)?sum*1.0/(n-1):minn;
        }
        printf("%d\n",(int)(minn*100));
    }
}

这个有个小技巧，按照一般写会超时各个点到一个点x的最短距离可以换成x到各个点的，只需把矩阵反转一下再跑一遍图论算法就可以了

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#define inf 0x3f3f3f
using namespace std;
int map[1010][1010];
int dis[1010];
int dis1[1010];
int vis[1010];
int n,m,x;
void djst(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    
    dis[s]=0;
    while(1)
    {
        int k=-1,minn=inf;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&dis[i]<minn)
            k=i,minn=dis[i];
        }
        if(k==-1) break;
        vis[k]=1;
        for(int i=1;i<=n;i++)
        dis[i]=min(dis[i],dis[k]+map[k][i]);
    }

}
int main()
{
     while(scanf("%d %d %d",&n,&m,&x)!=EOF)
    {
        memset(map,inf,sizeof(map));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j) map[i][j]=0;
                else map[i][j]=inf;
            }
        }
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            if(map[a][b]>c)
            map[a][b]=c;
        }
        djst(x);
        for(int i=1;i<=n;i++) dis1[i]=dis[i];
    
    /*    for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cout<<map[i][j]<<"    ";
            }
            cout<<endl;
        }
        cout<<endl;
            for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cout<<map[i][j]<<"    ";
            }
            cout<<endl;
        }
        */
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
            swap(map[i][j],map[j][i]);
            }
        }
        int ans=0;
        djst(x);
        for(int i=1;i<=n;i++)
        {
        //    cout<<dis[i]<<" "<<dis1[i]<<endl;
            ans=max(ans,dis[i]+dis1[i]);
        }
        cout<<ans<<endl;
    }

    return 0;
 }

这个有点难度把，注意先保证距离最短，再来判断价格

邻接矩阵回朝内存，要用邻接表的

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f
struct ac{
    int v,dis,cost;
};
int n,m;
int dis[10002];
int cost[10002];
int vis[10002];
vector<ac>rode[10002];
void djst()
{
    memset(dis,inf,sizeof(dis));
    memset(cost,inf,sizeof(cost));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    cost[1]=0;
    while(1) 
    {
        int k=-1,dmin=inf,cmin=inf;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j])
            {
                if(dis[j]<dmin)
                k=j,dmin=dis[j],cmin=cost[j];
                else if(dis[j]==dmin)
                {
                    if(cost[j]<cmin)
                    k=j,dmin=dis[j],cmin=cost[j];
                }
            }    
        }
        if(k==-1) return ;
        vis[k]=1;
        
        for(int i=0;i<rode[k].size();i++)
        {
            int j=rode[k][i].v;
            if(!vis[j])
            {
                if(dis[k]+rode[k][i].dis<dis[j])
                {
                    dis[j]=dis[k]+rode[k][i].dis;
                    cost[j]=rode[k][i].cost;
                }
                else if(dis[k]+rode[k][i].dis==dis[j]&&cost[j]>rode[k][i].cost)
                {
                    cost[j]=rode[k][i].cost;
                }
            }
        }
    }
}
int main()
{
    while(cin>>n>>m)
    {
        if(n+m==0) break;
        for(int i=1;i<=m;i++)
        {
            int a,c,b,d;
            cin>>a>>b>>c>>d;
            ac tt;
            tt.v=b,tt.dis=c,tt.cost=d;
            rode[a].push_back(tt);
            tt.v=a;
            rode[b].push_back(tt);
        }
        djst();
        int ans=0;
    //    for(int i=1;i<=n;i++)
    //    cout<<cost[i]<<"   ";
    //    cout<<endl;
        for(int i=1;i<=n;i++){
            rode[i].clear();
            ans+=cost[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

这个是超出内存的

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#define inf 0x3f3f3f
using namespace std;
int n,m;
int vis[10001];
int dis[10001];
int pre[10001];
int len[10001][10001];
int cost[10001][10001];
void prim()
{
    memset(dis,inf,sizeof(dis));
    memset(pre,inf,sizeof(pre));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    pre[1]=0;
    int sum=0;
    while(1)
    {
        
        int k=-1,dmin=inf,cmin;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                if(dis[i]<dmin)
                {
                    k=i;
                    dmin=dis[i];
                    cmin=pre[i];
                }
                else if(dis[i]==dmin){
                    if(pre[i]<cmin)
                    {
                        k=i;
                        dmin=dis[i];
                        cmin=pre[i];
                    }
                }
            }
        }
        if(k==-1) return;
        vis[k]=1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                    if(dis[i]>dis[k]+len[k][i])
                {
                    dis[i]=dis[k]+len[k][i];
                    pre[i]=cost[k][i];
                }
                else if(dis[i]==dis[k]+len[k][i]&&pre[i]>cost[k][i])
                {
                    pre[i]=cost[k][i];
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m),n+m){
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j) len[i][j]=len[j][i]=0,cost[i][j]=cost[j][i]=0;
                else len[i][j]=len[j][i]=inf,cost[i][j]=cost[j][i]=inf;
            }
        }
        while(m--){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            if(len[a][b]>c)
            len[a][b]=len[b][a]=c;
              if(cost[a][b]>d)
            cost[a][b]=cost[b][a]=d;
        }
        prim();
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=pre[i];
        }
        cout<<ans<<endl;
        
    }
}

要判断是否有负的权值

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int VM=520;
const int EM=2520;
const int INF=0x3f3f3f3f;

struct Edge{
    int u,v;
    int cap;
}edge[EM<<1];

int n,m,k;
int cnt,dis[VM];

void addedge(int cu,int cv,int cw){
    edge[cnt].u=cu;     edge[cnt].v=cv;     edge[cnt].cap=cw;
    cnt++;
}

int Bellman_ford(){
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[1]=0;
    for(int i=1;i<n;i++)    //n-1次松弛
        for(int j=0;j<cnt;j++)  //枚举每条边
            if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)
                dis[edge[j].v]=dis[edge[j].u]+edge[j].cap;
    for(int j=0;j<cnt;j++)
        if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)   //判断是否存在负权边
            return 0;
    return 1;
}

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        cnt=0;
        int u,v,w;
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        while(k--){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,-w);
        }
        int ans=Bellman_ford();
        printf("%s\n",ans==0?"YES":"NO");
    }
    return 0;
}

上一篇：组合模式

下一篇： Servlet浅谈

暑假图论练习

javaSE练习2——流程控制_2.2

页内跳转（锚点练习）的实例代码

数值计算画图练习记录

Jsの数组练习-求一组数中的最大值和最小值，以及所在位置

Python 练习题:DNA序列的基因片段检测

Python3练习题系列（09）——物以类聚，人以群分

正则表达式练习器

测试代码的练习——python编程从入门到实践

电子商务-简单建模（练习篇）

ASP.NET CORE[练习]-Identity-Assertion