codeforces #216前三题

前两题就直接粘代码了。。

题目地址：A. Valera and Plates

AC代码：

#include
  
   
#include
   
     using namespace std; int main() { int n,m,k,i; int t; while(cin>>n>>m>>k) { int ans=0; for(i=1;i<=n;i++) { scanf("%d",&t); if(t==1) { if(m) { m--; } else { ans++; } } else { if(k) { k--; } else if(m) { m--; } else ans++; } } cout<
    
     
 
     
 
     
 
     
题目地址：B. Valera and Contest
 
     
AC代码：
 
     

     
#include
      
       
#include
       
         using namespace std; int a[1002]; int main() { int n,k,l,r,sall,sk,i,j; int tmp,tn; while(cin>>n>>k>>l>>r>>sall>>sk) { tn=n-k; for(i=1; i<=n; i++) { if(sk==0) { //cout<
        
         
 
         
 
         
 
         

 
 
         
 C. Valera and Elections time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 
         
 The city Valera lives in is going to hold elections to the city Parliament.
 
         
 The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from 1 to n, inclusive. Furthermore, for each road the residents decided if it is the problem road or not. A problem road is a road that needs to be repaired.
 
         
 There are n candidates running the elections. Let's enumerate all candidates in some way by integers from 1 to n, inclusive. If the candidate number i will be elected in the city Parliament, he will perform exactly one promise ― to repair all problem roads on the way from the i-th district to the district 1, where the city Parliament is located.
 
         
 Help Valera and determine the subset of candidates such that if all candidates from the subset will be elected to the city Parliament, all problem roads in the city will be repaired. If there are several such subsets, you should choose the subset consisting of the minimum number of candidates.
 Input 
         
 The first line contains a single integer n (2 ≤ n ≤ 105) ― the number of districts in the city.
 
         
 Then n - 1 lines follow. Each line contains the description of a city road as three positive integers xi, yi, ti (1 ≤ xi, yi ≤ n, 1 ≤ ti ≤ 2) ― the districts connected by the i-th bidirectional road and the road type. If ti equals to one, then the i-th road isn't the problem road; if tiequals to two, then the i-th road is the problem road.
 
         
 It's guaranteed that the graph structure of the city is a tree.





 Output 
         
 In the first line print a single non-negative number k ― the minimum size of the required subset of candidates. Then on the second line print k space-separated integers a1, a2, ... ak ― the numbers of the candidates that form the required subset. If there are multiple solutions, you are allowed to print any of them.
 Sample test(s) input 
         
5
1 2 2
2 3 2
3 4 2
4 5 2
 output 
         
1
5 
 input 
         
5
1 2 1
2 3 2
2 4 1
4 5 1
 output 
         
1
3 
 input 
         
5
1 2 2
1 3 2
1 4 2
1 5 2
 output 
         
4
5 4 3 2 
 
         
 
         
 
         
 
         

 
 
         
题目不难，当时看见大概有六百+的人过了这题的样例，但是自己想不到怎么样来建图。。。题目意思不难理解，就是说有n个顶点，1，2.....n这样的定点，然后有n-1条边，确保是一颗树。边的值可以是1，代表这条路没问题，是2代表有问题。需要人来修，现在选人数最少的人来修所有为2的边。一个人可以修到1过程中走的路上的所有边。于是问他抽象出来就是找离1最远的点并且边是2这样的点。一直苦于不知如何建图。。。。
 
         

 
 
         
解题思路：
 
         
 
         
1）用vector数组保存每个节点的子节点；
 
         
2）深搜，找到每个节点的父节点，从而建立一棵树；
 
         
3）每个结点往上面找，如果这个点需要修路，把他自己设置为1，把他所有的父亲祖宗结点都变为0，并设置为访问过，访问过的就不再访问了。
 
 
         

 
 
         
题目地址：C. Valera and Elections
 
         

 
 
         
AC代码：
 
         

         
#include
          
           
#include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  using namespace std; const int maxn=100005; int visi[maxn]; //dfs建树的时候用 从叶子向根遍历的时候用 int par[maxn]; vector 
                 
                   mq[maxn]; int p[maxn]; struct node { int a; int b; int val; }; node road[maxn]; void dfs(int p) { for(int i=0;i
                  
                   >n) { memset(visi,0,sizeof(visi)); for(i=1;i<=n;i++) mq[i].clear(); for(i=0; i
                   
                    =1;i--) if(p[i]==1) { if(flag==0) { flag=1; printf("%d",i); } else printf(" %d",i); } cout<