蓝桥杯的安慰奶牛问题

Question

我用的是c++的prim算法，测试结果如下

            ![图片说明](https://img-ask.csdn.net/upload/201811/15/1542297344_260245.png)

       代码如下：

#include<iostream>
#include<stdio.h> 
#include<string.h>
#define MAX 1000000
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n+1][n+1];    
    int p;
    cin>>p;
    int q,w;
    int S[n+1];   
    for(q=1;q<=n;q++)
    {
        cin>>S[q];
    } 
    for(q=1;q<=n;q++)
        for(w=1;w<=n;w++)
        a[q][w]=MAX;
    while(p)
    {
        int t;
        cin>>q>>w>>t;
        a[q][w]=t;
        a[w][q]=t;
        p--;
    }
    for(q=1;q<=n;q++)
        for(w=1;w<=n;w++)
            if(a[q][w]<MAX) a[q][w]=a[q][w]*2+S[q]+S[w];  
    for(q=1;q<=n;q++)
        a[q][q]=0; 
    int Q[n+1]; 
        q=1;
        memset(Q,0,sizeof(Q)) ;
        Q[q]=1;
        int cost[n+1];
        for(int i=0;i<=n;i++)
        cost[i]=a[q][i];
        int j=2;
        int k=q;
        while(j<=n)
        {
            int min=MAX;
            int L;
            for(int i=1;i<=n;i++)
            {
                if(!Q[i]&&min>cost[i]) 
                {
                        min=cost[i];
                        L=i;
                }
            }
            Q[L]=1;
            for(int i=1;i<=n;i++)
            if(!Q[i]&&a[L][i]<cost[i])
                {       
                    cost[i]=a[L][i];
                }
                j++;
        }
        int sum=0;
        for(int i=1;i<=n;i++)
        sum+=cost[i];
        int b;
        int min=MAX;
         for(int i=1;i<n;i++)
            {
                b=sum+S[i];
                if(min>b) min=b;
            }
        cout<<min<<endl;
        return 0;
} 

是因为后面的几个输入数据特别大，导致数组过于大，内存不足而导致的错误吗？？？

Answer 1

int a[n+1][n+1];
堆栈不能放很大的数组，否则会爆栈
而且似乎你应该用动态规划，不能这么死算。