結果

問題 No.119 旅行のツアーの問題
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-08 17:44:14
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,984 bytes
コンパイル時間 1,277 ms
コンパイル使用メモリ 149,044 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-23 09:15:36
合計ジャッジ時間 2,314 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int, int)’:
main.cpp:18:25: warning: narrowing conversion of ‘g[t].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
  Edge a = { t, g[t].size(), 0, cap };
                ~~~~~~~~~^~
main.cpp:19:25: warning: narrowing conversion of ‘g[s].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
  Edge b = { s, g[s].size(), 0, cap };
                ~~~~~~~~~^~

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

const int maxnodes = 5000;

int nodes = maxnodes, src, dest;
int dist[maxnodes], q[maxnodes], work[maxnodes];

struct Edge {
	int to, rev;
	int f, cap;
};

vector<Edge> g[maxnodes];

// Adds bidirectional edge
void addEdge(int s, int t, int cap){
	Edge a = { t, g[t].size(), 0, cap };
	Edge b = { s, g[s].size(), 0, cap };
	g[s].push_back(a);
	g[t].push_back(b);
}

bool dinic_bfs() {
	fill(dist, dist + nodes, -1);
	dist[src] = 0;
	int qt = 0;
	q[qt++] = src;
	for (int qh = 0; qh < qt; qh++) {
		int u = q[qh];
		for (int j = 0; j < (int)g[u].size(); j++) {
			Edge &e = g[u][j];
			int v = e.to;
			if (dist[v] < 0 && e.f < e.cap) {
				dist[v] = dist[u] + 1;
				q[qt++] = v;
			}
		}
	}
	return dist[dest] >= 0;
}

int dinic_dfs(int u, int f) {
	if (u == dest)
		return f;
	for (int &i = work[u]; i < (int)g[u].size(); i++) {
		Edge &e = g[u][i];
		if (e.cap <= e.f) continue;
		int v = e.to;
		if (dist[v] == dist[u] + 1) {
			int df = dinic_dfs(v, min(f, e.cap - e.f));
			if (df > 0) {
				e.f += df;
				g[v][e.rev].f -= df;
				return df;
			}
		}
	}
	return 0;
}


int maxFlow(int _src, int _dest) {
	src = _src;
	dest = _dest;
	int result = 0;
	while (dinic_bfs()) {
		fill(work, work + nodes, 0);
		while (int delta = dinic_dfs(src, INT_MAX))
			result += delta;
	}
	return result;
}


int main() {
	int N, M;
	cin >> N;
	vector<int> B(N), C(N);
	for (int i = 0; i < N; i++)
	{
		cin >> B[i] >> C[i];
	}
	nodes = N + N + 2;

	int INF = (int) 1e9;
	int left = 0;
	int right = N;
	int start = N + N;
	int goal = N + N + 1;

	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int high = max(B[i], C[i]);
		ans += high;
		addEdge(start, left + i, high - B[i]);
		addEdge(left + i, right + i, high - C[i]);
		addEdge(right + i, goal, high);
	}

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int D, E;
		cin >> D >> E;
		addEdge(left + D, right + E, INF);
	}
	cout << ans << endl;
	ans -= maxFlow(start, goal);
	cout << ans << endl;
}
0