結果

問題 No.654 Air E869120
ユーザー vjudge1
提出日時 2025-05-21 11:53:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 77 ms / 2,000 ms
コード長 1,400 bytes
コンパイル時間 3,707 ms
コンパイル使用メモリ 279,300 KB
実行使用メモリ 31,640 KB
最終ジャッジ日時 2025-05-21 11:53:24
合計ジャッジ時間 6,274 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,C=1000005;
int n,m,d,u[N],v[N],p[N],q[N],w[N],s,t,cnt,ans,head[C],dep[C],cur[C];
struct edge
{
	int to,nxt,w,f;
}e[C];
void add(int u,int v,int w)
{
	e[cnt]={v,head[u],w,0};
	head[u]=cnt++;
}
void addrel(int u,int v,int w)
{
	add(u,v,w);
	add(v,u,0);
}
int bfs()
{
	queue<int> q;
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u],v,w,f;~i;i=e[i].nxt)
		{
			v=e[i].to;w=e[i].w;f=e[i].f;
			if(dep[v]||w<=f)continue;
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	return dep[t];
}
int dfs(int u,int rm)
{
	if(u==t||!rm)return rm;
	int res=0;
	for(int &i=cur[u],v,w,f,fl;~i;i=e[i].nxt)
	{
		v=e[i].to;w=e[i].w,f=e[i].f;
		if(dep[v]!=dep[u]+1)continue;
		fl=dfs(v,min(rm-res,w-f));
		if(!fl)continue;
		res+=fl;
		e[i].f+=fl;
		e[i^1].f-=fl;
		if(res==rm)return rm;
	}
	return res;
}
int dinic()
{
	int res=0;
	while(bfs())
	{
		memcpy(cur,head,sizeof(cur));
		res+=dfs(s,0x3f3f3f3f);
	}
	return res;
}
signed main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m>>d;t=2*m+1;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>p[i]>>q[i]>>w[i];
		if(u[i]==1)addrel(s,i,0x3f3f3f3f);
		if(v[i]==n)addrel(i+m,t,0x3f3f3f3f);
		addrel(i,i+m,w[i]);
	}
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(u[j]==v[i]&&p[j]>=q[i]+d)addrel(i+m,j,0x3f3f3f3f);
	cout<<dinic();
}
0