행복해지려면 몇 개? (JUNGOL 11187)

https://jungol.co.kr/problem/11187

---

아이디어

어떤 간선 E가 MST에 들어가기 위해서는 E보다 가중치가 낮은 간선들을 다 이었을 때 E의 양 끝점을 잇는 경로에서 최소 몇개의 간선을 끊어야하는지로 정의할 수 있습니다. 이는 최대유량-최소컷 정리에 의해서 E의 양 끝점을 시작점과 도착점으로 하는 최대 유량을 구해주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;

vector <ll> Graph[111];

ll MaxFlow(ll Start,ll End)
{
    ll res=0;
    ll Flow[111][111]={0},Cap[111][111]={0};

    for (ll i=1;i<=100;i++)
    {
        for (ll x:Graph[i])
            Cap[i][x]=1;
    }

    while (true)
    {
        ll Before[111]={0};
        queue <ll> q;

        q.push(Start);
        while (q.size())
        {
            ll now=q.front();
            q.pop();

            for (ll next:Graph[now])
            {
                if (Before[next]) continue;
                if (Flow[now][next]<Cap[now][next])
                {
                    q.push(next);
                    Before[next]=now;
                }
            }
        }

        if (Before[End]==0) break;

        ll mn=1e18,temp=End;
        while (temp!=Start)
            mn=min(mn,Cap[Before[temp]][temp]-Flow[Before[temp]][temp]),temp=Before[temp];
        res+=mn;
        temp=End;
        while (temp!=Start)
            Flow[Before[temp]][temp]+=mn,Flow[temp][Before[temp]]-=mn,temp=Before[temp];
    }
    
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,M,i,a,b,c;
    vector <array <ll,3> > Edge;

    cin>>N>>M;
    for (i=0;i<M;i++)
    {
        cin>>a>>b>>c;
        Edge.push_back({c,a,b});
    }

    ll res=0;
    for (i=0;i<M;i++)
    {
        for (ll j=1;j<=N;j++) Graph[j].clear();
        for (ll j=0;j<M;j++)
        {
            if (Edge[j][0]<Edge[i][0])
            {
                Graph[Edge[j][1]].push_back(Edge[j][2]);
                Graph[Edge[j][2]].push_back(Edge[j][1]);
            }
        }

        res+=MaxFlow(Edge[i][1],Edge[i][2]);
    }

    cout<<res;
}