codeforces #216 처음 세 문제

앞의 두 문제는 바로 코드를 붙였다.
제목 주소: A. Valera and Plates
AC 코드:

#include<iostream>
#include<cstdio>
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<<ans<<endl;
    }
    return 0;
}

제목 주소: B. Valera and Contest
AC 코드:

#include<iostream>
#include<cstdio>
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<<i<<endl;
                for(j=i; j<=n; j++)
                {
                    //cout<<sall<<" "<<tn<<endl;
                    tmp=sall/tn;
                    if(sall%tn) tmp++;
                    //cout<<tmp<<endl;
                    a[j]=tmp;
                    sall-=tmp;
                    tn--;
                }
                break;
            }
            tmp=sk/k;
            if(sk%k) tmp++;
            a[i]=tmp;
            sk-=tmp;
            sall-=tmp;
            k--;
        }

        cout<<a[1];
        for(i=2; i<=n; i++)
            cout<<" "<<a[i];
        cout<<endl;
    }
    return 0;
}

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 

문제는 어렵지 않았어요. 그때 약 600+의 사람들이 이 문제의 예시를 통과한 것을 보았는데 어떻게 그림을 지을지 몰랐어요...제목의 뜻은 이해하기 어렵지 않다. 즉, n개의 정점이 있다. 하나, 둘......n 이런 정점, 그리고 n-1변이 있어 나무임을 확보한다.변의 값은 1이 될 수 있다. 이 길은 문제없다는 뜻이고, 2가 문제가 있다는 뜻이다.수리할 사람이 필요합니다. 지금 가장 적은 사람을 뽑아서 2의 가장자리를 모두 수리합니다.한 사람이 1과정에서 걷는 길의 모든 가장자리를 수리할 수 있다.그래서 그에게 추상적으로 물어보면 1에서 가장 먼 점을 찾고 가장자리가 2라는 점을 찾는다.어떻게 설계해야 할지 몰라서 계속 고생했어...
문제 해결 방법:
1)vector 수조로 각 노드의 하위 노드를 저장한다.
2) 각 노드의 부모 노드를 샅샅이 뒤져 나무 한 그루를 세운다.
3) 각 결점을 위로 찾아라. 만약에 이 점을 수리해야 한다면 그 자신을 1로 설정하고 그의 모든 아버지 조상 결점을 0으로 설정하고 방문한 것으로 설정하면 방문한 것은 다시 방문하지 않는다.
제목 주소: C. Valera and Elections
AC 코드:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
const int maxn=100005;

int visi[maxn];  //dfs                  
int par[maxn];
vector <int> 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<mq[p].size();i++)
    {
        int cur=mq[p][i];
        if(!visi[cur])
        {
            visi[cur]=1;
            par[cur]=p;
            dfs(cur);
        }
    }
}

int main()
{
    int n,i;
    int l,r,v;
    while(cin>>n)
    {
        memset(visi,0,sizeof(visi));
        for(i=1;i<=n;i++)
            mq[i].clear();
        for(i=0; i<n-1; i++)     //             
        {
            scanf("%d%d%d",&l,&r,&v);
            road[i].a=l,road[i].b=r,road[i].val=v;
            mq[l].push_back(r);
            mq[r].push_back(l);
        }

        visi[1]=1;
        dfs(1);  // 1      

        memset(visi,0,sizeof(visi));
        memset(p,0,sizeof(p));
        for(i=0;i<n-1;i++)
        {
            l=road[i].a,r=road[i].b;
            v=road[i].val;
            int t;   //t     
            if(v==2)
            {
                if(par[l]==r)
                    t=l;
                else
                    t=r;

                if(!visi[t])
                {
                    p[t]=1;
                    int x=par[t];
                    while(x!=1)
                    {
                        if(visi[x]) break;
                        visi[x]=1;
                        p[x]=0;
                        x=par[x];
                    }
                }
            }
        }

        int ans=0;
        for(i=1;i<=n;i++)
            if(p[i]==1)
                ans++;
        cout<<ans<<endl;

        int flag=0;
        for(i=n;i>=1;i--)
            if(p[i]==1)
            {
                if(flag==0)
                {
                    flag=1;
                    printf("%d",i);
                }
                else
                    printf(" %d",i);
            }
        cout<<endl;
    }
    return 0;
}