Boj 2316) 도시 왕복하기 2

문제

백준 2316

설명

정점에 한번만 방문해야함. 이를 위해선 네트워크 플로우에 정점 분할을 더해야 함.

• 이는 기존 정점을 in-flow, out-flow 로 쪼개서 그 사이의 용량을 1로 하면 됨
• 이때 양방향 그래프이므로 1<-> 이면 1_in <-> 2_out, 2_out <-> 1_in 둘다 해줘야함.

Edmonds_Karps 로 풀었지만 Dinitz 로 풀면 더빠름.

시간 복잡도

O(\(V \times E^2\))

코드

const int MAX_IN = 402*2;

vector<int> lines[MAX_IN]; 
int c[MAX_IN][MAX_IN], f[MAX_IN][MAX_IN], d[MAX_IN];

#define T 2*2
#define S 1*2 + 1

int Edmonds_Karps()
{
	int ans = 0;
	while (1)
	{
		fill(d, d + MAX_IN, -1);

		queue<int> works;
		works.push(S);
		while (!works.empty()) 
		{
			int size = works.size();
			while (size--)
			{
				int cur = works.front();
				works.pop();
				for (auto l : lines[cur])
					if (c[cur][l] - f[cur][l] > 0 && d[l] == -1)
					{
						d[l] = cur; 
						works.push(l);
					}
			}
		}
	
		if (d[T] == -1) break;
		for (int i = T; i != S; i = d[i])
		{
			f[i][d[i]] -= 1;
			f[d[i]][i] += 1;
		}
		ans += 1;
	}
	return ans;
}

int main()
{
	int n, p;
	cin >> n >> p;
	
	for (int i = 2; i <= n<<1; i+=2)
	{
		lines[i].push_back(i+1);
		lines[i+1].push_back(i);
		c[i][i+1] = 1;
	}
	
	while(p--)
	{
		int from, to;
		cin >> from >> to;
		lines[from*2+1].push_back(to*2);
		lines[to*2].push_back(from*2+1);
		lines[from*2].push_back(to*2+1);
		lines[to*2+1].push_back(from*2);
		c[from*2+1][to*2] = 1; c[to*2+1][from*2] = 1;
	}
	
	cout << Edmonds_Karps();
}