사심경로를 구하는 문제이다.
사심경로란,
1. 남초 대학교와 여초 대학교끼리만 연결 되있다.
2. 어느 대학교에서든 모든 대학교와 연결 되있다.
3. 이 경로는 최단경로이다.
위 조건을 만족하는 경로이다.
즉, 이 문제는 남초 대학교와 여초 대학교가 연결된 간선으로만 이루어진 MST를 구하는 문제이다.
애초에 간선을 입력받을때 (남대,남대) 또는 (여대,여대)인 경우는 간선으로 입력 받지 않으면 된다.
이 문제를 풀때 다익스트라로 접근을 했었는데
2211 네트워크 복구 ttps://www.acmicpc.net/problem/2211
이 문제와 굉장히 유사하기 때문이다.
이 문제에서는 다음조건이 성립해야한다.
1. 1번컴퓨터는 슈퍼컴퓨터로 모든 컴퓨터와 연결되어있어야 한다.
2. 최소개수의 간선만 남겨야한다.
3. 2.의 간선들은 기존의 최단경로보다 느려서는 안된다.
1.과 2.조건만을 만족한다면 MST를 구하는 문제일 것이지만 3.에서 최단경로보다 느려서는 안되므로
이 문제는 다익스트라로 각 거리를 구해서 역으로 탐색하면 해결된다.
다시 돌아와서 정점4개와 간선4개로 이루어진 그래프를 예시로 들어보겠다.
이 그래프를 예시로 14621번(MST)을 풀면 1-2, 2-3, 3-4의 간선이 연결된 스패닝트리가 답이된다.
하지만 2211번(다익스트라)을 풀면 1-2, 2-3, 1-4의 간선이 연결된 스패닝트리가 답이된다.
(1-4는 2가 최단거리이기 때문)
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<int, int> MP;
#define mp(a,b) make_pair(a,b)
#define INF 987654321
int N, M;
char gender[1001];
int dist[1001];
vector<MP> adj[1001];
int di(int start){
int ans = 0;
bool visit[1001];
priority_queue<MP, vector<MP>, greater<MP>> pq;
fill(visit, visit + N + 1, false);
fill(dist, dist + N + 1, INF);
dist[start] = 0;
pq.push(mp(0, start));
while (!pq.empty()){
int here = pq.top().second;
int cost = pq.top().first;
pq.pop();
if (visit[here]) continue;
visit[here] = true;
ans += cost;
for (auto n : adj[here]){
if (!visit[n.second])
pq.push(n);
}
}
for (int n = 1; n <= N; n++) if (!visit[n]) return -1;
return ans;
}
int main(){
scanf("%d%d", &N, &M);
for (int n = 1; n <= N; n++)
scanf(" %c", &gender[n]);
for (int m = 0; m < M; m++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (gender[a] == gender[b]) continue;
adj[a].push_back(mp(c, b));
adj[b].push_back(mp(c, a));
}
const int start = 5;
printf("%d\n",di(start));
return 0;
}
| cs |
댓글 없음:
댓글 쓰기