結果

問題 No.654 Air E869120
ユーザー WA_TLEWA_TLE
提出日時 2018-02-23 23:13:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,713 bytes
コンパイル時間 1,975 ms
コンパイル使用メモリ 153,332 KB
実行使用メモリ 41,376 KB
最終ジャッジ日時 2024-10-10 02:34:21
合計ジャッジ時間 5,639 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,636 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;

const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
class dinic{
public:
	int n,sta,gol;
	vector<vector<llint>> hen;
	vector<int>dis;//bfsの距離
	//隣接行列(O(VVE)なので)
	dinic(int in,int s,int g){
		n=in;
		sta=s;
		gol=g;
		hen.res(in);
		dis.res(in);
		for(int i=0;i<n;i++){hen[i].res(in);}
	}
	void add(int u,int v,llint wei){hen[u][v]+=wei;}
	//隣接なので逆編情報が不要!!
	//増加のbfsする
	//それが増加する向きだけに流す
	//流れないなら、終了!
	void bfs(void){
		int i;
		for(i=0;i<n;i++){dis[i]=-1;}//初期化
		queue<pair<int,int>>que;
		que.push(mp(0,sta));
		dis[sta]=0;
		while(!que.empty()){
			
			int kyo=que.front().fir;
			int town=que.front().sec;
			que.pop();
			for(i=0;i<n;i++){
				if(hen[town][i]!=0&&dis[i]==-1){dis[i]=kyo+1;que.push(mp(kyo+1,i));}
			}
		}
	}
	llint dfs(int ter,llint lim){
		//それまでの上限がlim
		//流した量を返す
		if(ter==gol){return lim;}
		llint ans=0;
		int i;
		for(i=0;i<n;i++){
			if(dis[ter]>=dis[i]||hen[ter][i]==0){continue;}//dinic
			if(lim==ans){break;}
			llint nga=dfs(i,min(lim-ans,hen[ter][i]));
			ans+=nga;
			hen[ter][i]-=nga;
			hen[i][ter]+=nga;
		}
		return ans;
	}
	llint solve(void){
		llint ans=0;
		while(-1){
			bfs();
			llint nga=dfs(sta,big);
			ans+=nga;
			if(nga==0){break;}
		}
		return ans;
	}
};
int main(void){
	//♨♨フロー♨♨
	//はいフロー 貼るだけ界のtourist
	llint n,m,d,i,j;cin>>n>>m>>d;
	dinic gra(m+m,0,0);
	vector<vector<pair<llint,llint>>> zyu(n);
	for(i=0;i<m;i++){
		llint u,v,p,q,w;cin>>u>>v>>p>>q>>w;u--;v--;q+=d;
		gra.add(i+m,i,w);
		zyu[u].pub(mp(p,i+m));
		zyu[v].pub(mp(q,i));
	}
	for(i=0;i<n;i++){SO(zyu[i]);}
	for(i=0;i<n;i++){
		for(j=1;j<zyu[i].size();j++){
			gra.add(zyu[i][j-1].sec,zyu[i][j].sec,big);
		}
	}
	gra.sta=zyu[0][0].sec;
	gra.gol=zyu.back().back().sec;
	cout<<gra.solve()<<endl;RE;
}
0