竞赛讨论区 > 内存超限???
头像
小涂同学啦啦啦
编辑于 2020-11-11 09:27
+ 关注

内存超限???

//我自己算了一下空间,才十几KB啊?到底是什么原因让我内存超限了呢
//下面是代码
#include<iostream>
#include <algorithm>
#include<cstdio>
#include<string.h>
using namespace std;
typedef long long ll;
#define Int int
const ll MOD = 1e9 + 7, inf = 0x3f3f3f3f;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
template <typename T> inline void read(T& t) { t = 0; char c = getchar(); int f = 1; while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }while (c >= '0' && c <= '9') { t = (t << 3) + (t << 1) + c - '0'; c = getchar(); } t *= f; }
template <typename T, typename ... Args> inline void read(T& t, Args&... args) { read(t); read(args...); }
template <typename T> inline void write(T x) { if (x < 0) { x = -x; putchar('-'); }if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
enum { maxn = 1510, maxm = 1510 };
int head[maxn],nex[2*maxm],to[2*maxm], e_tot;
inline void add_edge(int from, int tto) {nex[++e_tot] = head[from];to[e_tot] = tto;head[from] = e_tot;}
inline void map_init(int n = maxn) {memset(head, 0xff, sizeof(head));e_tot = 0;}

int n,m;
char s[10];
int dp[2][maxn];
//dp[0] 该点有没有哨兵
void dfs(int u,int fa){
    dp[1][u]=1;dp[0][u]=0;
    for(int p=head[u];~p;p=nex[p]){
        int v=to[p];
        if(v==fa) continue;
        dfs(v,u);
        dp[1][u]+=min(dp[0][v],dp[1][v]);
        dp[0][u]+=dp[1][v];
    }
}
signed main(){
    int u,v;
    while(cin>>n){
        map_init();
        for(int i=0;i<n;++i){
            cin>>s;
            if(s[3]=='0')continue;
            int t=s[3]-'0',u=s[0]-'0';
            for(int i=0;i<t;++i){
                read(v);
                add_edge(u,v);
                add_edge(v,u);
            }
        }
        memset(dp,0,sizeof(dp));
        dfs(1,0);
        cout<<dp[1][1]<<endl;
    }
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐