前几天学了dinic,本来想写poj1273的,不过discuss里有组数据过不去。。我查了快俩小时了。。实在不知道哪错了。。跪求大牛帮我看看
(我觉得我的reverse那块有问题。。不过不是特别确定= =。。跪求大牛帮忙啊啊)
#include<iostream>
#include<fstream>
#define Inf 0x7fffffff
using namespace std;
ifstream fin("1.txt");
int n,cnt,first[1005],level[1005],ans=0;
struct edge
{
int next,pnt,remain,reverse;
}e[10005];
void Addedge(int x,int y,int z)
{
e[++cnt].next=first[x];
first[x]=cnt;
e[cnt].pnt=y;
e[cnt].remain=z;
e[cnt].reverse=cnt+1;
e[++cnt].next=first[y];
first[y]=cnt;
e[cnt].pnt=x;
e[cnt].remain=0;
e[cnt].reverse=cnt-1;
}
bool makelevel()
{
for(int i=1;i<=n;i++)
level[i]=-1;
int p=0,q=1,queue[1005];
queue[1]=1;level[1]=0;
while(p<q)
{
p++;
for(int i=first[queue[p]];i;i=e[i].next)
if(e[i].remain&&level[e[i].pnt]<0)
level[queue[++q]=e[i].pnt]=level[queue[p]]+1;
}
return level[n]>=0;
}
int MAXflow(int s,int flow)
{
if(s==n)return flow;
int maxflow=0,d;
for(int i=first[s];i;i=e[i].next)
{
if(level[e[i].pnt]==level[s]+1)
{
d=MAXflow(e[i].pnt,min(flow,e[i].remain));
if(d>0)
{
maxflow+=d;
e[i].remain-=d;
if(e[i].reverse)
e[i].reverse+=d;
}
}
}
if(!maxflow)level[s]=-1;
return maxflow;
}
void Dinic()
{
int d;
while(makelevel())
if(d=MAXflow(1,Inf))
ans+=d;
}
int main()
{
int m,i,j,s,t,x,y,z;
while(fin>>m>>n){
ans=0;cnt=0;
memset(first,0,sizeof(first));
while(m--)
{
fin>>x>>y>>z;
Addedge(x,y,z);
}
Dinic();
cout<<ans<<endl;
}
system("pause");
return 0;
}
(我觉得我的reverse那块有问题。。不过不是特别确定= =。。跪求大牛帮忙啊啊)
#include<iostream>
#include<fstream>
#define Inf 0x7fffffff
using namespace std;
ifstream fin("1.txt");
int n,cnt,first[1005],level[1005],ans=0;
struct edge
{
int next,pnt,remain,reverse;
}e[10005];
void Addedge(int x,int y,int z)
{
e[++cnt].next=first[x];
first[x]=cnt;
e[cnt].pnt=y;
e[cnt].remain=z;
e[cnt].reverse=cnt+1;
e[++cnt].next=first[y];
first[y]=cnt;
e[cnt].pnt=x;
e[cnt].remain=0;
e[cnt].reverse=cnt-1;
}
bool makelevel()
{
for(int i=1;i<=n;i++)
level[i]=-1;
int p=0,q=1,queue[1005];
queue[1]=1;level[1]=0;
while(p<q)
{
p++;
for(int i=first[queue[p]];i;i=e[i].next)
if(e[i].remain&&level[e[i].pnt]<0)
level[queue[++q]=e[i].pnt]=level[queue[p]]+1;
}
return level[n]>=0;
}
int MAXflow(int s,int flow)
{
if(s==n)return flow;
int maxflow=0,d;
for(int i=first[s];i;i=e[i].next)
{
if(level[e[i].pnt]==level[s]+1)
{
d=MAXflow(e[i].pnt,min(flow,e[i].remain));
if(d>0)
{
maxflow+=d;
e[i].remain-=d;
if(e[i].reverse)
e[i].reverse+=d;
}
}
}
if(!maxflow)level[s]=-1;
return maxflow;
}
void Dinic()
{
int d;
while(makelevel())
if(d=MAXflow(1,Inf))
ans+=d;
}
int main()
{
int m,i,j,s,t,x,y,z;
while(fin>>m>>n){
ans=0;cnt=0;
memset(first,0,sizeof(first));
while(m--)
{
fin>>x>>y>>z;
Addedge(x,y,z);
}
Dinic();
cout<<ans<<endl;
}
system("pause");
return 0;
}