hdu 3549 Dinic算法实现哪里有问题？
做这题用Dinic写了四次，两次RE，两个TLE，估计是陷入死循环了。后来用EK算法就过了。不过还想把问题找出来。在网上也看到一些dinic版的，但还是没改好。请各位帮忙看一下.ps:我是参考刘汝佳的训练指南写的.
代码如下：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define MAXN 1000
#define MAXEDGE 1000
#define INF 0x7fffffff
using namespace std;
struct Edge{
int from,to,cap,flow;
Edge(int f,int t,int c,int fl){
from=f,to=t,cap=c,flow=fl;
}
};
vector<Edge> edges;
vector<int> G[MAXN];//G[i][j]表示结点i的第j条边在e数组中的编号
int dis[MAXN];//i到起点的距离
int cur[MAXEDGE];//当前弧下标
int min(int a,int b){
return a<b?a:b;
}
void addEdge(int from,int to,int cap);
bool bfs(int s,int t);
int dfs(int x,int a,int t);
int maxFlow(int s,int t);
int main(){
int t,n,m;
scanf("%d",&t);
for(int kase=1;kase<=t;++kase){
scanf("%d%d",&n,&m);
edges.clear();
for(int i=0;i<=n;++i){
G[i].clear();
}
for(int i=1;i<=m;++i){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
}
printf("Case %d: %d\n",kase,maxFlow(1,n));
}
return 0;
}
void addEdge(int from,int to,int cap){
Edge tmp1(from,to,cap,0),tmp2(to,from,0,0);
edges.push_back(tmp1);
edges.push_back(tmp2);
int m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
int maxFlow(int s,int t){
int flow(0);
while(bfs(s,t)){
memset(cur,0,sizeof(cur));
flow+=dfs(s,INF,t);
}
return flow;
}
bool bfs(int s,int t){
bool vis[MAXN];
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);
dis[s]=0;
vis[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();++i){
Edge &e=edges[G[x][i]];
if(!vis[e.to] && e.cap>e.flow){
vis[e.to]=true;
dis[e.to]=dis[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a,int t){//t 汇点，也是点的总数
if(x==t || a==0 )
return a;
int flow=0,f;
for(int &i=cur[x];i<G[x].size();++i){
Edge &e=edges[G[x][i]];
if( dis[x]+1== dis[e.to] && e.cap>0 && ( f=dfs(e.to,min(a,e.cap-e.flow),t)>0 )){
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)
break;
}
}
return flow;
}
[解决办法]
( f=dfs(e.to,min(a,e.cap-e.flow),t)>0 )
括号配错了，直接导致答案出错。
