tr

Soruyu bir graph haline getirdiğimizde, sorunun aslında basit bir BFS (Breadth First Search) sorusu olduğunu görebiliriz. Sorunun BFS'ten tek farkı, her gün kurabileceği arkadaşlık sayısının kısıtlanmış olması. Bunu da her gün kurulan arkadaşlık sayısını \( K \) ile limitlersek çözmüş oluruz.

BFS'te her gün için \(T_{i}\)'yi (\(i\)'inci gün tanışabileceği arkadaş sayısını) hesaplayarak ve sonrasında da bunları sırayla toplamalıyız. \( K \) ile limitlemeyi de eğer bulduğumuz \(T_i\) sayısı \( K \)'dan büyükse sadece \( K \) kadar arkadaş edindiği için kurabileceği arkadaş sayısı yerine \( K \)'yı ekleyerek çözebiliriz. Burada dikkat etmemiz gereken yer ise eğer \(T_i\) sayısı \( K \)'dan fazla olduğunda sonraki günlerde o gün tanışabileceği, ama tanışmadığı insanlarla arkadaş olabileceği için, \( T_i - K \)'yı \( T_{i+1} \)'e eklemeliyiz.

BFS algoritması için ayrıntılı bilgi için bir kaynak.

en

If the problem is thought of as a graph, it can be seen that is a basic BFS problem. The only difference that the problem has is the number of friends met in a day is limited. This can be solved with a simple limit to the number of friends had on that day with \( K \).

With BFS \(T_i\) ( the number of people can be met in \(i\)'th day) can be found for every day and then all the \(T_i\)'s can be added to find the answer. Limiting with \( K \) can be done such as if the number \( T_i \) is bigger than \( K \) than only \( K \) must be added to the sum. The thing to watch out here is that if \( T_i \) is bigger than \(K\) than the difference should be added to \(T_{i+1}\) since the other people can be met in the following days.

A source for further information about BFS algorithm.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>

ll vis[300005], n, k, p, res=0, m, l, ind=1;
vector<ll> adj[300005];
map<ll, ll> ma;
queue<pll> q;
map<string, ll> id;

int main(){
    cin>>n>>m>>k>>l;
    for(int i=0;i<m;i++){
        string a, b;
        cin>>a>>b;
        if(!id[a]) id[a] = ind++;
        if(!id[b]) id[b] = ind++;

        adj[id[a]].push_back(id[b]);
        adj[id[b]].push_back(id[a]);
    }

    q.push({0, id["yiit"]}); 

    while(!q.empty()){
        pll u = q.front(); 
        q.pop();

        if(vis[u.second]) continue;
        else vis[u.second]=1;
        ma[u.first]++;

        for(auto x: adj[u.second]) q.push({u.first+1, x});
    }

    for(int i=1;i<=l;i++){
        res+=min(ma[i], k);
        ma[i+1]+=ma[i]-min(ma[i], k);
    }

    cout<<res<<endl;
}