首页 > 代码库 > 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