백준 2861 : 원섭동 사람들

문제 링크

힘들게 해결했다.

처음에 문제를 보고 사이클이 생겼을 때, 조금씩 빚을 상환해서 최소한의 돈으로 상환하는 것을 생각하고 풀었는데, 이 문제는 그런 게 아니라, 돈이 없으면 갚지 않고 있다가 돈을 시에서 지급해주던가, 다른 사람이 갚아서 돈이 생겨야지 일시불로 지불하는 문제였다. 그래서 엄청 틀렸다 ㅠ

이 문제를 보고 그래프를 떠올리는 것은 쉽게 할 수 있다. 각 정점에서 나가는 간선이 하나인 그래프를 떠올릴 수 있는데, 이러한 그래프는 연결되어 있는 요소만을 볼 때(dfs,bfs로 도달 가능) 사이클이 하나 존재한다는 것을 알 수 있다. 수학적 귀납법을 통해 증명할 수 있다.

사이클을 제외한 요소들에 대해서 생각해보면, indegree가 0인 정점은 무조건 시에서 지원을 해주어야 한다는 것을 알 수 있다. 따라서 위상정렬을 통해 사이클에 들어있지 않은 점들이 지원받아야 하는 돈을 계산해준다. 여기서 처음에 indegree가 0인 점을 제외하고는 지원할 돈을 계산할 때, 다른 사람들에게 돈을 받는 것도 고려해야한다는 것을 주의해야 한다.

이제 사이클에 있는 점들에 대해서 생각해봐야하는데 사이클 외부점의 간선들은 위상정렬을 진행할 때 이미 계산을 해주었으므로 제외하면, 사이클에서는 모든 점이 indegree와 outdegree가 1로 같다. 따라서 각 점들이 지원받아야 하는 돈은 max(0,나가는 간선 돈 - 들어오는간선 돈) 이다. 하지만 여기서 주의해야 하는 것은 사이클이 어디선가는 시작해야 된다는 것이다. 사이클이 시작하는 정점은 사이클에서 들어오는 돈을 받지 못하므로 각 정점에 대해서 사이클에 포함되지 않았을 때 내야하는 돈 - 사이클에 포함되어있을 때 내야 하는 돈 을 계산한 다음 그것이 가장 작은 정점부터 시작해서 사이클을 돌려주면 된다.

사이클을 시작할 때 가장 작게만 시작하면 된다고 생각해서 각 정점에 대해 나가는 돈 - 이미 들어온 돈을 계산하고 가장 작은 정점부터 시작했는데 맞았다..;; 사이클에서 들어오는 돈을 생각을 안했는데도. 아마 데이터가 약한거 같다. 날 잡아서 한번 반례 찾아봐야겠다. 이 풀이는 AC를 받은 후 대회 풀이를 보면서 잘못됨을 깨닫고 고친 풀이이다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21*1e8;
const int MAX = 1e9;

int n;
int ans = 0;

vector<int> sccin;
vector<int> indeg;
vector<pii> edge;
vector<int> discovered;
vector<bool> finished;
vector<vector<int>> scc;
vector<int> toplo;
vector<int> sccidx;
vector<pii> sccmin;
vector<int> in;
stack<int> s;
vector<int> tomon;
int discovcnt = 0;
int scccnt = 0;

int findscc(int cur)
{
    discovered[cur] = discovcnt++;
    s.push(cur);

    int ret = discovered[cur];

    int next = edge[cur].first;
    if(discovered[next] == -1)
    {
        ret = min(ret,findscc(next));
    }
    else if(!finished[next])
    {
        ret = min(ret,discovered[next]);
    }


    if(ret >= discovered[cur] && !finished[cur])
    {
        scc.push_back(vector<int>());
        int temp = INF;
        int idx = -1;
        while(1)
        {
            int stop = s.top();
            s.pop();

            scc[scccnt].push_back(stop);
            sccidx[stop] = scccnt;
            finished[stop] = true;
            if(edge[stop].second < temp)
            {
                temp = edge[stop].second;
                idx = stop;
            }
            if(stop == cur) break;
        }

        sccmin[scccnt] = {temp,idx};
        scccnt++;
    }

    return ret;
}

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;

    discovered = vector<int>(n,-1);
    finished = vector<bool>(n,false);
    sccidx = vector<int>(n);
    sccmin = vector<pii>(n);
    in = vector<int>(n,0);
    tomon = vector<int>(n);
    edge = vector<pii>(n);
    indeg = vector<int>(n,0);
    
    

    for(int i = 0;i<n;i++)
    {
        int to,m;
        cin>>to>>m;
        to--;

        edge[i] = {to,m};
        indeg[to]++;
    }

    for(int i = 0;i<n;i++)
    {
        if(discovered[i] == -1)
        {
            findscc(i);
        }
    }

    vector<bool> iscycle(scccnt,false);
    sccin = vector<int>(scccnt,0);

    for(int i = 0;i<scccnt;i++)
    {
        if(scc[i].size() > 1) iscycle[i] = true;
    }

    for(int i = 0;i<n;i++)
    {
        if(sccidx[i] != sccidx[edge[i].first] && iscycle[sccidx[edge[i].first]])
        {
            sccin[sccidx[edge[i].first]] += edge[i].second;
        }
    }
 
    queue<int> q;
    for(int i = 0;i<n;i++)
    {
        if(!indeg[i]) q.push(i);
    }

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        toplo.push_back(cur);

        if(edge[cur].second == 0) continue;

        if(--indeg[edge[cur].first] == 0) q.push(edge[cur].first);
    }


    int tsize = toplo.size();
    for(int i =0;i<tsize;i++)
    {
        int cur = toplo[i];

        ans += max(0,edge[cur].second - in[cur]);

        in[edge[cur].first] += edge[cur].second;
    }

    for(int i = 0;i<scccnt;i++)
    {
        if(iscycle[i])
        {
            int ssize = scc[i].size();
            ll temp = -1LL*INF*INF;
            int minidx = -1;
            for(int j = 0;j<ssize;j++)
            {
                int next = edge[scc[i][j]].first;

                ll f = max(edge[next].second - in[next] - edge[scc[i][j]].second,0);
                ll g = max(edge[next].second - in[next],0);          

                if(temp < f - g)
                {
                    temp = f-g;
                    minidx = next;
                }
            }
            int route = minidx;

            ans += max(0,edge[route].second - in[route]);
            in[edge[route].first] += edge[route].second;

            route = edge[route].first;

            for(;route != minidx;route = edge[route].first)
            {
                ans += max(0,edge[route].second - in[route]);
                in[edge[route].first] += edge[route].second;
            }
        }
    }

    cout<<ans;
    return 0;
}