冈崎梦美 @ 2018-03-09 22:34:59
RT……大概写的和刘汝佳的《算法竞赛入门经典(训练指南)》上的Dinic差不多,但是有点区别,结果就爆了……求改正
#include<bits/stdc++.h>
#define MAXN 10001
#define MAXM 100001
#define INF 1e9
using namespace std;
int level[MAXN];
vector<int>G[MAXN];
int m,n,s,t;
struct node
{
int from,to,cap,flow;
};
vector<node>edges;
void addedge(int u,int v,int cap)
{
edges.push_back((node){u,v,cap,0});
edges.push_back((node){v,u,0,0});
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool Dinic_BFS()
{
bool vis[MAXN]={false};
queue<int>team;team.push(s);
level[s]=0;vis[s]=true;
while(!team.empty())
{
int q=team.front();
for(int i=0;i<G[q].size();i++)
{
node& e=edges[G[q][i]];
if (!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=true;
level[e.to]=level[q]+1;
team.push(e.to);
}
}
}
return vis[t];
}
int Dinic_DFS(int u, int cpflow) {
if(u==t) return cpflow;
int flow=0;
for(int i=0;i<G[u].size() && flow<cpflow; i++){
int v=edges[G[u][i]].to;
if((level[u]+1==level[v])&&(edges[G[u][i]].cap>edges[G[u][i]].flow))
{
int tmpflow=Dinic_DFS(v,min(cpflow-flow,edges[G[u][i]].cap-edges[G[u][i]].flow));
edges[G[u][i]].flow+=tmpflow;
edges[G[u][i]^1].flow-=tmpflow;
flow+=tmpflow;
}
}
return flow;
}
int Dinic(int s,int t)
{
int ans=0;
while(Dinic_BFS())
{
memset(level,0,sizeof(level));
ans+=Dinic_DFS(s,INF);
}
return ans;
}
int read()
{
char ch;int x=0;
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
int main()
{
n=read();m=read();s=read();t=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),c=read();
addedge(u,v,c);
}
cout<<Dinic(s,t);
return 0;
}
by star_magic_young @ 2018-03-10 07:50:33
你用队列不pop? /huaji
by 冈崎梦美 @ 2018-03-10 10:13:22
@star_magic_young 通过了,谢谢Dalao
by 冈崎梦美 @ 2018-03-10 10:14:16
需要注意的是,我的level的初始化也错了——level应该在Dinic_BFS函数里初始化
by heyichong @ 2018-03-21 19:31:49
一定要初始化