結果

問題 No.119 旅行のツアーの問題
ユーザー fura
提出日時 2020-11-30 06:01:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,543 bytes
コンパイル時間 2,573 ms
コンパイル使用メモリ 206,076 KB
最終ジャッジ日時 2025-01-16 10:20:31
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:83:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |         int n; scanf("%d",&n);
      |                ~~~~~^~~~~~~~~
main.cpp:98:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |                 int b,c; scanf("%d%d",&b,&c);
      |                          ~~~~~^~~~~~~~~~~~~~
main.cpp:108:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  108 |         int m; scanf("%d",&m);
      |                ~~~~~^~~~~~~~~
main.cpp:110:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |                 int x,y; scanf("%d%d",&x,&y);
      |                          ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

template<class capa_t>
class mf_graph{
	struct edge{
		int to,rev;
		capa_t capa,flow;
		edge(int to,int rev,const capa_t& capa,const capa_t& flow):to(to),rev(rev),capa(capa),flow(flow){}
	};

	vector<vector<edge>> G;
	vector<int> layer,cur;

	bool make_layer(int s,int t){
		int n=G.size();
		rep(u,n) layer[u]=(u==s?0:-1);

		queue<int> Q; Q.emplace(s);
		while(!Q.empty()){
			int u=Q.front(); Q.pop();
			for(const edge& e:G[u]) if(layer[e.to]==-1 && e.capa-e.flow>0) {
				layer[e.to]=layer[u]+1;
				if(e.to==t) return true;
				Q.emplace(e.to);
			}
		}
		return false;
	}

	capa_t augment(int u,int t,const capa_t& water){
		if(u==t) return water;

		for(int& i=cur[u];i<G[u].size();i++){
			edge& e=G[u][i];
			if(layer[e.to]>layer[u] && e.capa-e.flow>0){
				capa_t w=augment(e.to,t,min(water,e.capa-e.flow));
				if(w>0){
					e.flow+=w;
					G[e.to][e.rev].flow-=w;
					return w;
				}
			}
		}
		return 0;
	}

public:
	mf_graph(){}
	mf_graph(int n):G(n){}

	void add_directed_edge(int u,int v,const capa_t& capa){
		G[u].emplace_back(v,G[v].size()  ,capa,0);
		G[v].emplace_back(u,G[u].size()-1,   0,0);
	}

	void add_undirected_edge(int u,int v,const capa_t& capa){
		G[u].emplace_back(v,G[v].size()  ,capa,0);
		G[v].emplace_back(u,G[u].size()-1,capa,0);
	}

	capa_t maximum_flow(int s,int t){
		int n=G.size();
		layer.resize(n);

		capa_t res=0;
		while(make_layer(s,t)){
			cur.assign(n,0);
			for(capa_t water=1;water>0;res+=water){
				water=augment(s,t,numeric_limits<capa_t>::max());
			}
		}
		return res;
	}
};

const int INF=1<<29;

int main(){
	int n; scanf("%d",&n);

	/*
		(s, s) : ツアーなし
		(s, t) : 行かない
		(t, t) : ツアーあり
	*/
	mf_graph<int> G(2*n+2);
	int s=2*n,t=2*n+1;
	rep(i,n){
		G.add_directed_edge(n+i,i,INF); // (t, s) の可能性を排除
	}

	int sum=0;
	rep(i,n){
		int b,c; scanf("%d%d",&b,&c);
		int mx=max(b,c);
		sum+=mx;
		// 行かない場合, mx 円の罰金
		G.add_directed_edge(i,n+i,mx);
		// ツアーありの場合, mx-b 円の罰金
		G.add_directed_edge(s,i,mx-b);
		// ツアーなしの場合, mx-c 円の罰金
		G.add_directed_edge(n+i,t,mx-c);
	}
	int m; scanf("%d",&m);
	rep(i,m){
		int x,y; scanf("%d%d",&x,&y);
		// x がツアーあり => y はツアーあり or 行かない
		// すなわち, x がツアーあり and y がツアーなしの場合, ∞ 円の罰金
		G.add_directed_edge(n+y,x,INF);
	}

	printf("%d\n",sum-G.maximum_flow(s,t));

	return 0;
}
0