結果

問題 No.654 Air E869120
コンテスト
ユーザー vjudge1
提出日時 2025-05-21 11:38:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 1,520 bytes
コンパイル時間 1,926 ms
コンパイル使用メモリ 165,464 KB
実行使用メモリ 10,720 KB
最終ジャッジ日時 2025-05-21 11:38:43
合計ジャッジ時間 2,917 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:74:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |         scanf("%lld%lld%lld",&n,&m,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:77:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |                 scanf("%lld%lld%lld%lld%lld",&E[i].x,&E[i].y,&E[i].p,&E[i].q,&E[i].v);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define N 1005
using namespace std;
struct Edge{
	int x,y,p,q,v;
}E[N];
int n,m,d,Cnt,S,T;
int he[N*2],ne[2*N*N],t[2*N*N],v[2*N*N],tot=1;
void add(int x,int y,int z)
{
	ne[++tot]=he[x];
	he[x]=tot;
	t[tot]=y;
	v[tot]=z;
}
void Add(int x,int y,int v)
{
	add(x,y,v);
	add(y,x,0);
}
int dep[N*2],cur[N*2];
queue<int>q;
int bfs()
{
	while(!q.empty())q.pop();
	q.push(S);
	memset(dep,0,sizeof(dep));
	dep[S]=1;
	cur[S]=he[S];
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=he[x];i;i=ne[i])
		{
			if(!v[i]||dep[t[i]])continue;
			dep[t[i]]=dep[x]+1;
			cur[t[i]]=he[t[i]];
			q.push(t[i]);
			if(t[i]==T)return 1;
		}
	}
	return 0;
}
int dfs(int x,int flow)
{
	if(x==T)return flow;
	int res=flow;
	for(int i=cur[x];res&&i;i=ne[i])
	{
		cur[x]=i;
		if(dep[t[i]]!=dep[x]+1||!v[i])continue;
		int k=dfs(t[i],min(res,v[i]));
		if(!k)dep[t[i]]=0;
		v[i]-=k;
		v[i^1]+=k;
		res-=k;
	}
	return flow-res;
}
int Solve()
{
	int k,ans=0;
	while(bfs())
		while(k=dfs(S,inf))
			ans+=k;
	return ans;
}
signed main()
{

	scanf("%lld%lld%lld",&n,&m,&d);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld%lld%lld",&E[i].x,&E[i].y,&E[i].p,&E[i].q,&E[i].v);
		E[i].q+=d;
	}
	S=m+m+1;T=m+m+2;
	for(int i=1;i<=m;i++)
	{
		Add(i,m+i,E[i].v);
		if(E[i].x==1)
			Add(S,i,inf);
		if(E[i].y==n)
			Add(m+i,T,inf);
		for(int j=1;j<=m;j++)
			if(i!=j&&E[i].y==E[j].x&&E[i].q<=E[j].p)
				Add(m+i,j,inf);
	}
	int Ans=Solve();
	printf("%lld\n",Ans);
	return 0;
}
0