結果

問題 No.654 Air E869120
ユーザー WA_TLEWA_TLE
提出日時 2018-02-23 23:25:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 91 ms / 2,000 ms
コード長 3,864 bytes
コンパイル時間 2,282 ms
コンパイル使用メモリ 150,820 KB
最終ジャッジ日時 2025-01-05 08:34:08
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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)なので)
	vector<vector<int>>tna;
	//hen[town][i]>0 を探す
	dinic(int in,int s,int g){
		n=in;
		sta=s;
		gol=g;
		hen.res(in);
		dis.res(in);
		tna.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;tna[u].pub(v);tna[v].pub(u);}
	//隣接なので逆編情報が不要!!
	//増加の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(auto i:tna[town]){
				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;
		for(auto i:tna[ter]){
			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);
		}
	}
	if(zyu[0].size()==0||zyu[n-1].size()==0){cout<<"0\n";RE;}
	gra.sta=zyu[0][0].sec;
	gra.gol=zyu.back().back().sec;
	cout<<gra.solve()<<endl;RE;
}
0