QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93059#143. 最大流(随机数据)ExplodingKonjac#Compile Error//C++171.6kb2023-03-31 10:27:522023-03-31 10:27:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-31 10:27:57]
  • 评测
  • [2023-03-31 10:27:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

template<int MAXN,int MAXM,typename FlowT>
class MFGraph
{
 private:
	struct Edge{ int to,nxt;FlowT f; }e[MAXM*2+5];
	int cnt,head[MAXN+5],headd[MAXN+5],dep[MAXN+5];
	inline void __addEdge(int u,int v,FlowT f) { e[++cnt]=(Edge){v,head[u],f},head[u]=cnt; }
	bool bfs(int S,int T)
	{
		static int hd,tl,q[MAXN+5];
		memset(dep,0,sizeof(dep));
		memcpy(headd,head,sizeof(head));
		q[hd=tl=1]=S,dep[S]=1;
		for(int u=q[hd];(hd++)<=tl;u=q[hd])
			for(int i=head[u],v;v=e[i].to,i;i=e[i].nxt)
				if(e[i].w && !dep[v])
					dep[v]=dep[u]+1,q[++tl]=v;
		return dep[T];
	}
	FlowT dfs(int u,int T,FlowT flow=numeric_limits<FlowT>::max())
	{
		if(u==T || !flow) return flow;
		FlowT res(flow);
		for(int &i=headd[u],v;(v=e[i].to);i=e[i].nxt)
			if(e[i].f && dep[v]==dep[u]+1)
			{
				FlowT c=dfs(v,T,min(flow,e[i].f));
				e[i].f-=c,e[i^1].f+=c;
				if(!(res-=c)) break;
			}
		if(res==flow) dep[u]=0;
		return flow-res;
	}
 public:
	MFGraph() { clear(); }
	inline void clear()
		{ cnt=1,memset(head,0,sizeof(head)); }
	inline void addEdge(int u,int v,FlowT f)
		{ __addEdge(u,v,f),__addEdge(v,u,0); }
	inline FlowT maxFlow(int S,int T)
	{
		FlowT res(0);
		while(bfs(S,T)) res+=dfs(S,T);
		return res;
	}
};

int n,m,S,T;
MFGraph<100,5000,LL> g;
int main()
{
#ifndef DADALZY
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
#endif
	cin>>n>>m>>S>>T;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g.addEdge(u,v,w);
	}
	cout<<g.maxFlow(S,T);
	return 0;
}

详细

answer.code: In instantiation of ‘bool MFGraph<MAXN, MAXM, FlowT>::bfs(int, int) [with int MAXN = 100; int MAXM = 5000; FlowT = long long int]’:
answer.code:51:9:   required from ‘FlowT MFGraph<MAXN, MAXM, FlowT>::maxFlow(int, int) [with int MAXN = 100; int MAXM = 5000; FlowT = long long int]’
answer.code:71:17:   required from here
answer.code:24:41: error: ‘struct MFGraph<100, 5000, long long int>::Edge’ has no member named ‘w’
   24 |                                 if(e[i].w && !dep[v])
      |                                    ~~~~~^