//我自己算了一下空间,才十几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) 回帖