YangQuijote @ 2018-04-09 17:50:31
按照板子打的,但就是不对。。。仔细对比了板子也没发现哪里有问题
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,s,t,h[10010],mem=0,d[10010],cont[10010],ans=0,cur[10010],path[10010],length=0;
bool vis[10010];
struct neartable
{
int father,num,nex,c,p,re;
}ne[200010];
void add(int u,int v,int w)
{
++mem;
ne[mem].num=v;
ne[mem].nex=h[u];
ne[mem].c=w;
ne[mem].p=0;
ne[mem].re=mem+1;
ne[mem].father=u;
h[u]=mem;
++mem;
ne[mem].num=u;
ne[mem].nex=h[v];
ne[mem].c=w;
ne[mem].p=w;
ne[mem].re=mem-1;
ne[mem].father=v;
h[v]=mem;
}
void bfs()
{
int x,i;
queue<int>q;
q.push(t);
vis[t]=true;
d[t]=0;
++cont[0];
while(!q.empty())
{
x=q.front();
q.pop();
for(i=h[x];i!=0;i=ne[i].nex)
{
if(vis[ne[i].num]==false&&ne[ne[i].re].c>ne[ne[i].re].p)
{
vis[ne[i].num]=true;
d[ne[i].num]=d[x]+1;
q.push(ne[i].num);
++cont[d[ne[i].num]];
}
}
}
}
void getans()
{
int i,mi;
mi=ne[path[length]].c-ne[path[length]].p;
for(i=length-1;i>=1;i--)
{
mi=min(mi,(ne[path[i]].c-ne[path[i]].p));
}
for(;length>=1;length--)
{
ne[path[length]].p+=mi;
ne[ne[path[length]].re].p-=mi;
printf("%d ",ne[path[length]].num);
}
printf("%d ",ne[path[1]].father);
printf("%d\n",mi);
ans+=mi;
}
void init()
{
int i,u,v,w;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for(i=1;i<=n;i++)
{
cur[i]=h[i];
}
}
int main()
{
freopen("flow.in","r",stdin);
freopen("flow1.out","w",stdout);
int i;
init();
bfs();
int x=s,mi;
bool flag;
while(d[s]<n)
{
if(x==t)
{
x=s;
getans();
}
flag=false;
for(i=cur[x];i!=0;i=ne[i].nex)
{
if(d[ne[i].num]+1==d[x]&&ne[i].c>ne[i].p)
{
cur[x]=i;
++length;
path[length]=i;
flag=true;
x=ne[i].num;
break;
}
}
if(flag==false)
{
mi=1000010;
for(i=h[x];i!=0;i=ne[i].nex)
{
if(ne[i].c>ne[i].p)
{
mi=min(d[ne[i].num],mi);
}
}
--cont[d[x]];
if(cont[d[x]]==0)
{
break;
}
d[x]=mi+1;
++cont[d[x]];
cur[x]=h[x];
if(x!=s)
{
x=ne[path[length]].father;
}
}
}
printf("%d",ans);
return 0;
}
by feng_chengjie @ 2018-04-09 17:52:13
Dinic多好打。。。
by strangers @ 2018-04-09 18:32:28
EK多好打。。。
by iotang @ 2018-04-09 19:44:00
代码明显有问题,你本机是怎么A的。。。