不见得都用上了
by 良月澪二 @ 2018-10-14 18:11:24
@[LinkedIn](/space/show?uid=78064) 大佬，除了used和当前弧还有什么有话可以加吗？？
by Cyan_rose @ 2018-10-14 19:15:28
@[Cyan_rose](/space/show?uid=48246) 打错了，优化
by Cyan_rose @ 2018-10-14 19:15:41
你的dinic怎么这么长，而且比之前的EK还慢
by 良月澪二 @ 2018-10-14 19:25:49
@[LinkedIn](/space/show?uid=78064) 我就是很好奇这一点。。。我怀疑是哪个地方打错了，但一直没调试出来。
by Cyan_rose @ 2018-10-14 19:27:25
emm，上面的代码有误，但改了之后还是过不去。。（我莫非学了个假的Dinic。。）
```cpp
#include<bits/stdc++.h>
#define endll '\n'
#define rint register int
#define ivoid inline void
#define iint inline int
#define ull unsigned long long
#define ll long long
#define clude1 {
#define clude2 }
using namespace std;
const int N=1e7+5;
const int M=10010;
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
struct Edge{
int from;
int to;
int val;
int last;
int cost;
}edge[N];
int n,m,st,en,from,to,val,cost,q;
int vis[N],nxt[N],deep[N],cur[N],dis[N];
int mx=-inf,my=inf;
int sum_flow,sum_cost,st_en;
int cnt=1;
iint rad()
{
ll ret=0,f=1;
char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
ret=(ret<<3)+(ret<<1)+c-'0';
return ret*f;
}
ivoid addedge_cost(int x,int y,int z,int r)
{
edge[++cnt]=(Edge){x,y,z,nxt[x],r},nxt[x]=cnt;
edge[++cnt]=(Edge){y,x,0,nxt[y],-r},nxt[y]=cnt;
}
queue<int> dl1;
iint SPFA_Dinic(int x)
{
for(rint i=1;i<=n;i++)
cur[i]=nxt[i],vis[i]=0,dis[i]=inf;
dis[x]=0;
dl1.push(x);
while(dl1.size()){
q=dl1.front();
dl1.pop();
vis[q]=0;
for(rint i=nxt[q];i;i=edge[i].last){
if(dis[edge[i].to]>dis[q]+edge[i].cost&&edge[i].val){
dis[edge[i].to]=dis[q]+edge[i].cost;
if(!vis[edge[i].to]){
vis[edge[i].to]=1;
dl1.push(edge[i].to);
}
}
}
}
return dis[en]!=inf;
}
int Dfs_Dinic_Cost(int now,int can_flow)
{
if(now==en){
vis[en]=1;
sum_flow+=can_flow;
return can_flow;
}
int have_flow;
int used=0;
vis[now]=1;
for(rint i=cur[now];i;i=edge[i].last){
cur[now]=i;
if(dis[edge[i].to]==dis[now]+edge[i].cost&&edge[i].val){
if(vis[edge[i].to]==0||edge[i].to==en){
have_flow=Dfs_Dinic_Cost(edge[i].to,min(can_flow-used,edge[i].val));
if(have_flow){
used+=have_flow;
sum_cost+=have_flow*edge[i].cost;
edge[i].val-=have_flow;
edge[i^1].val+=have_flow;
if(used==can_flow)
break;
}
}
}
}
return used;
}
ivoid Dinic()
{
while(SPFA_Dinic(st)){
vis[en]=1;
while(vis[en]){
memset(vis,0,sizeof(vis));
Dfs_Dinic_Cost(st,inf);
}
}
}
#define read(x) x=rad()
int main()
{
// freopen("water.in","r",stdin);
read(n);read(m);read(st);read(en);
for(rint i=1;i<=m;i++)
{
read(from);read(to);read(val);read(cost);
addedge_cost(from,to,val,cost);
}
Dinic();
cout<<sum_flow<<" "<<sum_cost;
}
```
by Cyan_rose @ 2018-10-14 21:11:17