首页 > 代码库 > UVA1218 Perfect Service
UVA1218 Perfect Service
Time Limit: 3000MS | 64bit IO Format: %lld & %llu |
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std;10 const int mxn=20000;11 vector<int>e[mxn];12 int f[mxn][5];13 int vis[mxn];14 int n;15 void dp(int u){16 int i,j;17 vis[u]=1;18 f[u][0]=1;f[u][1]=0;f[u][2]=mxn;19 queue<int>q;20 for(i=0;i<e[u].size();i++){21 int v=e[u][i];22 if(!vis[v]){23 dp(v);24 q.push(v);25 f[u][0]+=min(f[v][1],f[v][0]);26 f[u][1]+=f[v][2];27 }28 }29 while(!q.empty()){30 f[u][2]=min(f[u][2],f[u][1]-f[q.front()][2]+f[q.front()][0]);31 q.pop();32 }33 return;34 }35 int main(){ 36 int i,j;37 while(scanf("%d",&n) && n!=-1){38 if(!n)continue;39 memset(f,0,sizeof f);40 memset(vis,0,sizeof vis);41 for(i=1;i<=n;i++) e[i].clear();42 int x,y;43 for(i=1;i<n;i++){44 scanf("%d%d",&x,&y);45 e[x].push_back(y);46 e[y].push_back(x);47 }48 dp(1);49 printf("%d\n",min(f[1][0],f[1][2]));50 }51 return 0;52 }
UVA1218 Perfect Service
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。