結果

問題 No.119 旅行のツアーの問題
ユーザー vjudge1vjudge1
提出日時 2024-12-21 18:54:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,502 bytes
コンパイル時間 1,486 ms
コンパイル使用メモリ 161,356 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 18:54:43
合計ジャッジ時間 2,470 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 2 ms
6,816 KB
testcase_17 AC 3 ms
6,816 KB
testcase_18 AC 2 ms
6,820 KB
testcase_19 AC 2 ms
6,820 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

struct Edge{
	int v,nxt;
	int c;
};

#define MAXN 85
#define MAXM 10005

int n,m;
int x,y;
int s;
Edge e[MAXM*2]; int h[MAXN],ec;
int cur[MAXN],dis[MAXN];
int qu[MAXN],fr,bk;

int en;
void adde(int u,int v,int c){
	e[ec].v=v,e[ec].nxt=h[u],e[ec].c=c;
	h[u]=ec; ++ec;
	return;
}
void addp(int u,int v,int c){
	// std::cout<<u<<' '<<v<<' '<<c<<'\n';
	adde(u,v,c),adde(v,u,0);
	return;
}
bool bfs(int s,int t){
	memset(dis,0x3f,sizeof(dis));
	
	qu[fr=bk=1]=s; dis[1]=0;
	while(fr<=bk){
		int u=qu[fr++];
		for(int i=h[u];i+1;i=e[i].nxt){
			int v=e[i].v;
			if(!e[i].c) continue;
			if(dis[u]+1<dis[v]) qu[++bk]=v,dis[v]=dis[u]+1;
		}
	}
	return dis[t]!=0x3f3f3f3f;
}
int dfs(int u,int t,int f){
	if(u==t) return f;
	int cnt=0;
	for(;cur[u]+1;cur[u]=e[cur[u]].nxt){
		int v=e[cur[u]].v; int c=e[cur[u]].c;
		if(dis[u]+1!=dis[v]||(!c)) continue;
		int now=dfs(v,t,std::min(f,c));
		f-=now,cnt+=now; e[cur[u]].c-=now,e[cur[u]^1].c+=now;
		if(!f) break;
	}
	return cnt;
}
int dinic(int s,int t){
	int res=0;
	while(bfs(s,t)){
		for(int i=1;i<=en;i++) cur[i]=h[i];
		res+=dfs(s,t,0x3f3f3f3f);
	}
	return res;
}

int main(){
	std::ios::sync_with_stdio(false);
	
	memset(h,-1,sizeof(h));
	
	std::cin>>n; en=2*n+2;
	for(int i=1;i<=n;i++){
		std::cin>>x>>y;
		addp(1,2*i,x),addp(2*i+1,2*n+2,y);
		s+=(x+y);
		addp(2*i,2*i+1,0x3f3f3f3f);
	}
	std::cin>>m;
	for(int i=1;i<=m;i++){
		std::cin>>x>>y; ++x,++y;
		addp(2*x,2*y+1,0x3f3f3f3f);
	}
	std::cout<<s-dinic(1,2*n+2)<<'\n';
	
	return 0;
}
0