Augury @ 2023-02-19 11:28:31
萌新刚学网络流，不知道为什么代码跑的很慢
这个是刚写的，用的前向星，跑了
这个是以前用邻接矩阵写的，才
萌新很疑惑，再次向各位dalao求助
by Augury @ 2023-02-19 11:29:09
前向星代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=210;
const int inf=1e15;
int n,m,s,t;
struct edge{
int u,v,val,nxt;
};
int fst[maxn],cur[maxn],cnt=0;
edge E[10010];
int dep[maxn];
void add(int u,int v,int w){
E[cnt]=(edge){u,v,w,fst[u]};
fst[u]=cnt;
++cnt;
}
bool bfs(){
memset(dep,-1,sizeof(dep));
queue<int>q;
q.push(s);
dep[s]=0;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=fst[now];i!=-1;i=E[i].nxt){
edge nxt=E[i];
// cout<<now<<' '<<nxt.v<<' '<<nxt.val<<endl;
if(nxt.val<=0)continue;
if(dep[nxt.v]!=-1)continue;
dep[nxt.v]=dep[now]+1;
q.push(nxt.v);
}
}
// for(int i=1;i<=n;i++)cout<<dep[i]<<' ';
// cout<<endl;
if(dep[t]!=-1)return 1;
return 0;
}
int dfs(int now,int a){
// cout<<now<<' '<<a<<endl;
if(now==t||a==0)return a;
int ans=0;
for(int i=fst[now];i!=-1;i=E[i].nxt){
cur[now]=i;
edge nxt=E[i];
if(nxt.val<=0||dep[nxt.v]!=dep[now]+1)continue;
int tmp=dfs(nxt.v,min(a,nxt.val));
if(tmp==0)dep[nxt.v]=inf;
a-=tmp;
E[i].val-=tmp;
E[i^1].val+=tmp;
ans+=tmp;
}
return ans;
}
int dinic(){
int maxflow=0;
for(int i=1;i<=n;i++)cur[i]=fst[i];
while(bfs()){
maxflow+=dfs(s,inf);
}
return maxflow;
}
signed main(){
memset(fst,-1,sizeof(fst));
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
// for(int i=1;i<=n;i++){
// for(int j=fst[i];j!=-1;j=E[j].nxt){
// cout<<E[j].v<<' '<<E[j].val<<',';
// }
// cout<<endl;
// }
// for(int i=0;i<cnt;i++)cout<<E[i].u<<' '<<E[i].v<<' '<<E[i].w<<' '<<E[i].nxt<<'\n';
// bfs();
cout<<dinic();
return 0;
}by World_Creater @ 2023-02-19 11:41:21
你这个当前弧不是假了
by UperFicial @ 2023-02-19 11:43:34
你的 cur 有什么用
by UperFicial @ 2023-02-19 11:44:02
只进不出
by Augury @ 2023-02-19 13:05:24
哦哦哦wssb
by Augury @ 2023-02-19 13:05:34
感谢各位大佬
by Augury @ 2023-02-19 13:13:13
@UperFicial 改了，但是还是很慢
by UperFicial @ 2023-02-19 14:32:33
@Augury
我的链式前向星才 90ms：
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
inline ll read_ll()
{
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
return s*w;
}
const int MAXN=10010;
const int MAXM=200010;
int n,m,s,t;
int head[MAXN],tot=1;
int depth[MAXN];
queue<int>q;
ll ans;
struct E
{
int to,nxt;
ll cost;
};
E edge[MAXM];
inline void add_edge(int u,int v,ll w)
{
edge[++tot].nxt=head[u];
head[u]=tot;
edge[tot].to=v;
edge[tot].cost=w;
return;
}
inline ll Min(ll x,ll y){return x<y?x:y;}
inline bool bfs()
{
memset(depth,0,sizeof(depth));
q.push(s);
depth[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(register int i=head[u];i;i=edge[i].nxt)
{
E e=edge[i];
if(e.cost&&!depth[e.to])
{
depth[e.to]=depth[u]+1;
q.push(e.to);
}
}
}
return depth[t];
}
inline ll dfs(int u,ll get)
{
if(u==t) return get;
ll put=0;
for(register int i=head[u];i&&get;i=edge[i].nxt)
{
E e=edge[i];
if(e.cost&&depth[e.to]==depth[u]+1)
{
ll now=dfs(e.to,Min(e.cost,get));
edge[i].cost-=now;
edge[i^1].cost+=now;
get-=now;
put+=now;
}
}
if(put==0) depth[u]=0;
return put;
}
int main()
{
n=read(),m=read(),s=read(),t=read();
while(m--)
{
int u=read(),v=read();
ll w=read_ll();
add_edge(u,v,w),add_edge(v,u,0);
}
while(bfs()) ans+=dfs(s,1e18);
printf("%lld\n",ans);
return 0;
}by Augury @ 2023-02-19 14:39:20
@UperFicial 又改了一下，到100ms了
by UperFicial @ 2023-02-19 14:40:39
@Augury 当前弧优化其实感觉没有什么明显优化。