結果

問題 No.654 Air E869120
コンテスト
ユーザー hoget
提出日時 2018-02-24 00:39:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 2,652 bytes
コンパイル時間 2,078 ms
コンパイル使用メモリ 180,700 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-10 11:11:18
合計ジャッジ時間 3,282 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void add_edge(long long int, long long int, long long int)':
main.cpp:35:51: warning: narrowing conversion of 'G[to].std::vector<edge>::size()' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   35 |         G[from].push_back((edge){to,cap,G[to].size()});
      |                                         ~~~~~~~~~~^~
main.cpp:36:54: warning: narrowing conversion of '(G[from].std::vector<edge>::size() - 1)' from 'std::vector<edge>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   36 |         G[to].push_back((edge){from,0,G[from].size() - 1});
      |                                       ~~~~~~~~~~~~~~~^~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+15;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct edge{int to,cap,rev; };

vector<edge> G[20000];
int level[20000],iter[20000];

void add_edge(int from,int to,int cap){
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size() - 1});
}

void bfs(int s){
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while(!que.empty()){
		int v = que.front();que.pop();
		for(int i = 0;i < G[v].size();i++){
			edge &e = G[v][i];
			if(e.cap > 0 && level[e.to] < 0){
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

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

int max_flow(int s,int t){
	int flow = 0;
	while(1){
		bfs(s);
		if(level[t] < 0) return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f = dfs(s,t,INF)) > 0) flow += f;
	}
}

signed main(){
	int n,m,d,ans = 0,u[1000],v[1000],p[1000],q[1000],w[1000],cnt = 0;
	vector<int> tim[1000],ind[1000];
	cin >> n >> m >> d;
	for(int i = 0;i < m;i++){
		cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i]; u[i]--;v[i]--;q[i] += d;
		tim[u[i]].pb(p[i]);
		tim[v[i]].pb(q[i]);
	}
	for(int i = 0;i < n;i++){
		sort(all(tim[i]));
		tim[i].erase(unique(all(tim[i])),tim[i].end());
		for(int j = 0;j < tim[i].size();j++){
			if(j) add_edge(cnt - 1,cnt,INF);
			ind[i].pb(cnt++);
		}
	}
	for(int i = 0;i < m;i++){
		int ind1 = lower_bound(all(tim[u[i]]),p[i]) - tim[u[i]].begin();
		int ind2 = lower_bound(all(tim[v[i]]),q[i]) - tim[v[i]].begin();
		add_edge(ind[u[i]][ind1],ind[v[i]][ind2],w[i]);
	}
	if(ind[0].size() && ind[n - 1].size()) ans = max_flow(ind[0][0],ind[n - 1].back());
	cout << ans << endl;
	return 0;
}
0