結果

問題 No.119 旅行のツアーの問題
ユーザー ey429ey429
提出日時 2015-03-05 11:40:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,093 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 39,424 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-01 06:52:28
合計ジャッジ時間 1,145 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 3 ms
6,940 KB
testcase_22 AC 3 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’:
main.cpp:15:44: warning: narrowing conversion of ‘e[v].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   15 |         e[u].push_back((edge){v,c,e[v].size()});
      |                                   ~~~~~~~~~^~
main.cpp:16:46: warning: narrowing conversion of ‘(e[u].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   16 |         e[v].push_back((edge){u,0,e[u].size()-1});
      |                                   ~~~~~~~~~~~^~
main.cpp: In function ‘int main()’:
main.cpp:48:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:56:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |                 scanf("%d %d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
main.cpp:66:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |                 scanf("%d %d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<string.h>
#include<vector>
#define V 82
#define INF 100000000
using namespace std;
struct edge{
	int to,cap,rev;
};

vector<edge> e[V];
bool used[V];

void add_edge(int u,int v,int c){
	e[u].push_back((edge){v,c,e[v].size()});
	e[v].push_back((edge){u,0,e[u].size()-1});
}

int dfs(int v,int t,int f){
	if(v==t)return f;
	used[v]=true;
	for(int i=0;i<e[v].size();i++){
		edge &g=e[v][i];
		if(!used[g.to]&&g.cap>0){
			int d=dfs(g.to,t,min(f,g.cap));
			if(d>0){
				g.cap-=d;
				e[g.to][g.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s,int t){
	int ans=0;
	while(1){
		memset(used,0,sizeof(used));
		int f=dfs(s,t,INF);
		if(f==0)return ans;
		ans+=f;
	}
}

int main(){
	int n,i;
	scanf("%d",&n);
	//0
	//1~n
	//n+1~n*2
	//n*2+1
	int s=0;
	for(i=0;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		s+=a+b;
		add_edge(0,i+1,a);
		add_edge(n+i+1,n*2+1,b);
		add_edge(i+1,n+i+1,INF);
	}
	int m;
	scanf("%d",&m);
	for(i=0;i<m;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		add_edge(a+1,n+b+1,INF);
	}
	printf("%d\n",s-max_flow(0,n*2+1));
	return 0;
}
0