首页 > 代码库 > ACM3371超时问题

ACM3371超时问题

2024-07-12 20:48:38   218人阅读

这的确也是个大坑；

其实在这是到很简单的最小生成树的题目，但是数据量却很大；

用G++提交会超时，用C++不会超时，而且速度超快；

又长见识了。可惜长得不是做题的能力，而是知道它到底有多坑。

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int N=600; 5 const int oo=11111111; 6 int map[N][N]; 7 int vis[N]; 8 int n,m,k; 9 int low[N];10 int prim(int s)11 {12     memset(vis,0,sizeof(vis));13     for(int i=1;i<=n;i++)14     low[i]=map[s][i];15     low[s]=0;16     vis[s]=1;17     int sum=0,v;18     for(int i=1;i<n;i++)19     {20         int Min=oo;21         for(int j=1;j<=n;j++)22             if(!vis[j]&&low[j]<Min)23             {24             Min=low[j];v=j;25             }26         if(Min==oo)return -1;27         sum+=Min;28         vis[v]=1;29         for(int j=1;j<=n;j++)30         {31             if(!vis[j]&&low[j]>map[j][v])32             low[j]=map[j][v];33         }34     }35     return sum;36 }37 int main()38 {39     int t;40     scanf("%d",&t);41     while(t--)42     {43         scanf("%d %d %d",&n,&m,&k);44         for(int i=1;i<=n;i++)45         for(int j=1;j<=n;j++)46         {47             map[i][j]=oo;48         }49         int a,b,c;50         for(int i=1;i<=m;i++)51         {52             scanf("%d %d %d",&a,&b,&c);53             if(map[a][b]>c)map[a][b]=map[b][a]=c;54         }55         int ct,room[N];56         for(int i=1;i<=k;i++)57         {58             scanf("%d",&ct);59             for(int j=1;j<=ct;j++)60             {61                 scanf("%d",&room[j]);62             }63             for(int j=1;j<=ct;j++)64             for(int s=j+1;s<=ct;s++)65             {66                 map[room[s]][room[j]]=map[room[j]][room[s]]=0;67             }68         }69         int result=prim(1);70         printf("%d\n",result);71     }72     return 0;73 }


联系
我们