QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93059 | #143. 最大流(随机数据) | ExplodingKonjac# | Compile Error | / | / | C++17 | 1.6kb | 2023-03-31 10:27:52 | 2023-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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]) | ~~~~~^