[백준] 14286 간선 끊어가기 2

문제

정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제거해 나갈 것이다. 이때, 특정 정점 s와 t가 비연결이 되는 시점에서 간선 제거를 멈출 것이다. 비연결이란 두 정점이 간선을 통해 방문 불가능한 것을 말한다.

s와 t가 비연결이 되는 시점의 지운 간선의 가중치의 합이 최소가 되게 제거하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

입력

첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤500,1≤m≤10,000)

다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다.(1≤a,b≤n,1≤c≤100,a≠b)

다음 줄에는 두 정점 s,t가 주어진다.(1≤s,t≤n,s≠t)

출력

s와 t가 비연결되는 시점의 지운 간선의 가중치 합의 최솟값을 출력하시오,

 

간선을 하나씩 지우면서 두 정점이 끊어지는 가장 작은 컷을 구하는 문제입니다

max flow minimum cut 문제입니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
//정점 구조체
struct Edge {
	//t: 목적지
	//c: capacity
	//f: flow
	int t, c, f=0;
	//생성자
	Edge(int to,int cap):t(to),c(cap){}

	//역간선 포인터
	Edge* rev;

	//capacity-flow
	int R() {
		return c - f;
	}
	//유량을 흘립니다
	void F(int a) {
		f += a;
		rev->f -= a;
	}
};
//간선을 만듭니다.
//간선은 양방향입니다 in>>out방향의 간선을 양쪽으로 두개만듭니다.

int N, M, vnum, S, E;
int f, t, c, s;
char mp[102][102];
int v[202][202];
//정점의 크기는 N*M*2 입니다
vector<vector<Edge*>>adj(503);


int MC() {
	int source = s;
	int sink = t;
	int total_flow = 0;
	//에드먼드 카프 알고리즘
	while (1) {
		int p[502];
		fill(p, p + 502, -1);
		vector<Edge*> edge_to_child(502);
		queue<int>q;
		q.push(source);
		p[source] = source;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (auto e : adj[cur]) {
				if (e->R() > 0 && p[e->t]==-1) {
					p[e->t] = cur;
					edge_to_child[e->t] = e;
					q.push(e->t);
				}
			}
		}
		if (p[sink] == -1)break;
		int flow = INF;
		for (int i = sink; i != source; i = p[i]) {
			Edge* ptoc = edge_to_child[i];
			flow = min(flow, ptoc->R());
		}
		for (int i = sink; i != source; i = p[i]) {
			edge_to_child[i]->F(flow);
		}
		total_flow += flow;
	}
	return total_flow;
}


int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		cin >> f >> t >> c;
		Edge* e = new Edge(t, c);
		Edge* e2 = new Edge(f, c);

		e->rev = e2;
		e2->rev = e;

		adj[f].push_back(e);
		adj[t].push_back(e2);
	}
	cin >> s >> t;
	cout << MC();
}