QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#480269 | #143. 最大流(随机数据) | ItheaValgulious# | Compile Error | / | / | C++14 | 1.7kb | 2024-07-16 11:59:15 | 2024-07-16 11:59:18 |
Judging History
This is the latest submission verdict.
- [2024-07-16 11:59:18]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-07-16 11:59:15]
- Submitted
answer
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<array>
#define endl '\n'
using namespace std;
using ll = long long;
using pi2 = array<int,2>;
using pi3 = array<int,3>;
int n,m;
const int N=100+50,M=5e3+50;
struct Edge{
int u,v,w,nxt;
} edges[M*2];
int head[N],ecnt;
void add_edge_(int u,int v,int w){
edges[++ecnt]={u,v,w,head[u]};
head[u]=ecnt;
}
void add_edge(int u,int v,int w){
add_edge_(u,v,w),add_edge_(v,u,0);
}
int cpy[N],dis[N];
bool bfs(int s,int t){
memcpy(cpy,head,sizeof(cpy)),memset(dis,0x3f,sizeof(dis));
queue<int> q;
q.push(s),dis[s]=0;
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=edges[i].nxt){
if(edges[i].w&&dis[edges[i].v]>dis[edges[i].u]+1){
dis[edges[i].v]=dis[edges[i].u]+1;
q.push(edges[i].v);
}
}
}
return dis[t]<=n;
}
ll dfs(int u,int t,int minf){
if(u==t||!minf)return minf;
ll f,flow=0;
for(int &i=cpy[u];i;i=edges[i].nxt){
if(edges[i].w&&dis[edges[i].v]==dis[edges[i].u]+1&&(f=dfs(edges[i].v,t,min(edges[i].w,minf)))){
flow+=f,minf-=f,edges[i].w-=f,edges[((i-1)^1)+1].w+=f;
if(!minf)return flow;
}
}
return flow;
}
ll dinic(int s,int t){
ll flow=0;
while(bfs(s,t))
flow+=dfs(s,t,INT32_MAX);
return flow;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
}
cout<<dinic(s,t)<<endl;
return 0;
}
详细
answer.code: In function ‘ll dinic(int, int)’: answer.code:58:23: error: ‘INT32_MAX’ was not declared in this scope 58 | flow+=dfs(s,t,INT32_MAX); | ^~~~~~~~~ answer.code:8:1: note: ‘INT32_MAX’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’? 7 | #include<array> +++ |+#include <cstdint> 8 | #define endl '\n'