글 읽기 - mcmf & ccw를 이용해서풀어봤는데 틀렸습니다 도와주세요..ㅜ

isvara 4년 전 0

우선 최대비용을 구해야하기때문에 모든 비용을 음으로 계산해서 최단거리를 구하고 마지막에 -를 곱해주도록 했고

ccw활용해서 연결시켰습니다.

질문글을보니 끝점을 고려하셔야한다고하시는데

끝점까지 고려해서 0일때도 연결을 시키도록 구현을 했는데도 틀리는군요 ..

Tc랑 갠적으로 만들어본 예제 몇개는돌아가는데 혹시 반례나 코드에서 잘못된부분이 있다면 지적부탁드립니다.

#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<cstring>
#include<string.h>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
struct line {
	ll x1, y1;
	ll x2, y2;
	int w;
};
//일단 최대 정점의 개수  402개
int n, m;//가로선0~199    세로선199~399  
const int ROW = 199;
const int SOURCE = 400;
const int SINK = 401;
const int INF = 987654321;
 

int capacity[402][402];//용량
int flow[402][402];//유량
int d[402][402];//비용
vector<int>adj[402];//연결

vector<line>col;//가로
vector<line>row;//세로

pair<int,int> mcmf() {
	int result = 0;
	int connected = 0;

	while (true) {
		vector<int>parent=vector<int>(402,-1);
		vector<int>dist=vector<int>(402,INF);
		int inQue[402];
		queue<int> q;

		memset(inQue, 0, sizeof(inQue));
		
		q.push(SOURCE);
		inQue[SOURCE] = 1;
		parent[SOURCE] = SOURCE;
		dist[SOURCE] = 0;

 		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			inQue[cur] = 0;

			for (int i = 0; i < adj[cur].size(); i++) {
				int next_v = adj[cur][i];
				int cost = d[cur][next_v];

				if (capacity[cur][next_v] - flow[cur][next_v] > 0 && dist[next_v] > dist[cur] + cost)
				{
					dist[next_v] = dist[cur] + cost;
					parent[next_v] = cur;

					if (!inQue[next_v]) {
						q.push(next_v);
						inQue[next_v] = 1;
					}
				}
			}
		}
		if (parent[SINK] == -1)
			break;

		int amount = INF;
		//유량 search
		for (int i = SINK; i != parent[i]; i = parent[i]) {
			amount = min(amount, capacity[parent[i]][i] - flow[parent[i]][i]);
		}
 		//유량 찾기
		for (int i = SINK; i != parent[i]; i = parent[i]) {
 			flow[parent[i]][i] += amount;
			flow[i][parent[i]] -= amount;    //parent[i][i]로 썻다..반대쪽 유량이니까 반대로 했어야
			result += amount * d[parent[i]][i];
		}
		connected += amount;
	}
	return pair<int,int>(connected,result);
}
ll ccw(pair<ll, ll>p1, pair<ll, ll>p2,pair<ll, ll>p3) {
	return ((p1.first * p2.second + p2.first * p3.second + p3.first * p1.second) - (p2.first*p1.second+p3.first*p2.second+p1.first*p3.second));
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		//초기화
		memset(capacity, 0, sizeof(capacity));
		memset(flow, 0, sizeof(flow));
		memset(d, 0, sizeof(d));
		col.clear();
		row.clear();
		for (int i = 0; i < 402; i++)
			adj[i].clear();

		//입력
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			ll x1, y1, x2, y2;
			int w;
			cin >> x1 >> y1 >> x2 >> y2>>w;
			col.push_back({ x1,y1,x2,y2,w });
		}
		for (int i = 0; i < m; i++) {
			ll x1, y1, x2, y2;
			int w;
			cin >> x1 >> y1 >> x2 >> y2 >> w;
			row.push_back({ x1,y1,x2,y2,w });
		}

		//연결

		//소스->가로
		for (int i = 0; i < n; i++) {
			//연결상태
			adj[SOURCE].push_back(i);
			adj[i].push_back(SOURCE);

			//용량
			capacity[SOURCE][i] = 1;
		}
		//가로->세로
		for(int i=0; i<n; i++)
			for (int j = 0; j < m; j++) {
				line l1 = col[i];
				line l2 = row[j];  ///이부분 row인데 col로 잘못 코딩했음..

				pair<ll, ll>p1 = pair<ll, ll>(l1.x1, l1.y1);
				pair<ll, ll>p2 = pair<ll, ll>(l1.x2, l1.y2);

				pair<ll, ll>p3 = pair<ll, ll>(l2.x1, l2.y1);
				pair<ll, ll>p4 = pair<ll, ll>(l2.x2, l2.y2);

				if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)
				{
					//연결상태
					adj[i].push_back(j + ROW);
					adj[j + ROW].push_back(i);
					//용량
					capacity[i][j + ROW] = 1;
					
					//비용
					d[i][j + ROW] = -1 * (l1.w * l2.w);
					d[j + ROW][i] = l1.w * l2.w;
				}
			}
		//세로->싱크
		for (int j = 0; j < m; j++) {
			//연결상태
			adj[SINK].push_back(j + ROW);
			adj[j + ROW].push_back(SINK);
			//용량
			capacity[j + ROW][SINK] = 1;
		}
		pair<int, int>ans = mcmf();
		cout << ans.first << " " << -1 * ans.second << endl;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

mcmf & ccw를 이용해서풀어봤는데 틀렸습니다 도와주세요..ㅜ

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말