我在写这道题的时候,刚开始我是这么写的:
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;
struct node{
long long v,w,nxt;
}e[maxn];
long long head[maxn],dpt[maxn],cur[maxn],cnt;
long long max_flow,t;
int n,m,x;
void add(long long x,long long y,long long z){
e[++cnt].v=y;
e[cnt].w=z;
e[cnt].nxt=head[x];
head[x]=cnt;
}
bool bfs(){
queue<int> q;
for(int i=1;i<=n;i++)
dpt[i]=0;
dpt[1]=1;
q.push(1);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=e[i].nxt){
int y=e[i].v;
if(e[i].w>0&&dpt[y]==0){
q.push(y);
dpt[y]=dpt[now]+1;
if(y==n)return 1;
}
}
}
return 0;
}
long long dfs(long long x,long long flow){
if(x==n)return flow;
long long res=flow;
for(int i=cur[x];i&&flow;i=e[i].nxt){
cur[x]=i;
long long y=e[i].v;
if(e[i].w>0&&dpt[y]==dpt[x]+1){
long long k=dfs(y,min(res,e[i].w));
if(k==0)dpt[y]=0;
e[i].w-=k;
e[i^1].w+=k;
res-=k;
}
}
return flow-res;
}
int main(){
cin>>n>>m>>x;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,0);
}
int flow=0;
while(bfs()){
for(int i=1;i<=n;i++)
cur[i]=head[i];
while(flow=dfs(1,1<<29))max_flow+=flow;
}
if(max_flow==0)puts("Orz Ni Jinan Saint Cow!");
else{
t=x/max_flow;
if(x%max_flow!=0)t++;
cout<<max_flow<<" "<<t;
}
return 0;
}
结果我只拿到了80pts
但是我后来把cnt的初值设成了1,结果AC了这道题,有没有大佬能给我解释一下其中的问题吗