結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー 古寺いろは
提出日時 2015-04-08 18:08:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,960 bytes
コンパイル時間 1,773 ms
コンパイル使用メモリ 162,788 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-21 10:48:22
合計ジャッジ時間 2,291 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int, int)’:
main.cpp:18:32: warning: narrowing conversion of ‘g[t].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   18 |         Edge a = { t, g[t].size(), 0, cap };
      |                       ~~~~~~~~~^~
main.cpp:19:32: warning: narrowing conversion of ‘g[s].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   19 |         Edge b = { s, g[s].size(), 0, 0 };
      |                       ~~~~~~~~~^~

ソースコード

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, 0 };
	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 - C[i]);
		addEdge(left + i, right + i, high);
		addEdge(right + i, goal, high - B[i]);
	}

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