LXH5514 @ 2021-05-25 14:14:17
第一种 : 边从0开始编号,邻接表first数组初始化为-1,能A, 提交记录
第二种 : 边从2开始编号,邻接表初始化为0,只有70分。 提交记录
第一种代码:
#include<iostream>
#include<stdio.h>
#include<queue>
#define int long long
using namespace std;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
return x*f;
}
const int MAXN=5000*2,inf=0x7ffffff;
int n,m,s,t;
int u[MAXN],v[MAXN],first[MAXN],net[MAXN],val[MAXN],res[MAXN];
int cnt=0;
int first1[MAXN];
int level[MAXN];
void add(int x,int y,int z)
{
u[cnt]=x;
v[cnt]=y;
val[cnt]=z;
net[cnt]=first[x];
first[x]=cnt;
first1[x]=cnt;cnt++;
}
bool BFS()
{
for(int i=1;i<=n;i++)
first[i]=first1[i];
for(int i=1;i<=n;i++)
level[i]=0;
level[s]=1;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=first[x];i!=-1;i=net[i])
if(level[v[i]]==0&&val[i]!=0)level[v[i]]=level[x]+1,q.push(v[i]);
}
if(level[t]==0)return 0;
return 1;
}
int dfs(int x,int y)
{
if(x==t||y==0)return y;
int sum=0;
for(int i=first[x];i!=-1&&y-sum>0;i=net[i])
{
first[x]=i;
if(level[v[i]]<=level[x]||val[i]==0)continue;
if(sum==y)break;
int z=dfs(v[i],min(val[i],y-sum));
sum+=z;
val[i]-=z;
val[i^1]+=z;
}
return sum;
}
void liu()
{
int ans=0;
while(BFS())ans+=dfs(s,inf);
printf("%lld\n",ans);
}
signed main()
{
n=read();
m=read();
s=read();
t=read();
for(int i=1;i<=n;i++)
first[i]=-1;
for(int i=1;i<=m;i++)
{
int x,y,z;
x=read();
y=read();
z=read();
add(x,y,z);
add(y,x,0);
}
liu();
return 0;
}
第二种:
#include<iostream>
#include<stdio.h>
#include<queue>
#define int long long
using namespace std;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
return x*f;
}
const int MAXN=5000*2,inf=0x7ffffff;
int n,m,s,t;
int u[MAXN],v[MAXN],first[MAXN],net[MAXN],val[MAXN],res[MAXN];
int cnt=1;
int first1[MAXN];
int level[MAXN];
void add(int x,int y,int z)
{
cnt++;
u[cnt]=x;
v[cnt]=y;
val[cnt]=z;
net[cnt]=first[x];
first[x]=cnt;
first1[x]=cnt;
}
bool BFS()
{
for(int i=1;i<=n;i++)
first[i]=first1[i];
for(int i=1;i<=n;i++)
level[i]=0;
level[s]=1;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=first[x];i;i=net[i])
if(level[v[i]]==0&&val[i]!=0)level[v[i]]=level[x]+1,q.push(v[i]);
}
if(level[t]==0)return 0;
return 1;
}
int dfs(int x,int y)
{
if(x==t||y==0)return y;
int sum=0;
for(int i=first[x];i&&y-sum>0;i=net[i])
{
first[x]=i;
if(level[v[i]]<=level[x]||val[i]==0)continue;
if(sum==y)break;
int z=dfs(v[i],min(val[i],y-sum));
sum+=z;
val[i]-=z;
val[i^1]+=z;
}
return sum;
}
void liu()
{
int ans=0;
while(BFS())ans+=dfs(s,inf);
printf("%lld\n",ans);
}
signed main()
{
n=read();
m=read();
s=read();
t=read();
// for(int i=1;i<=n;i++)
// first[i]=-1;
for(int i=1;i<=m;i++)
{
int x,y,z;
x=read();
y=read();
z=read();
add(x,y,z);
add(y,x,0);
}
liu();
return 0;
}
核心代码基本没差,就是一些细节差别
by IntrepidStrayer @ 2021-05-25 14:28:31
你数组开小了
by LXH5514 @ 2021-05-25 14:31:10
%%%%% @star_duster
by Plozia @ 2021-05-25 14:31:16
maxn
随手加上 10 是个好习惯
by Plozia @ 2021-05-25 14:31:27
@LXH5514
by LXH5514 @ 2021-05-25 15:24:00
主要是我一开始只开了一倍的时候随手加了10,然后改成两倍就忘记加了
by 王瑞eggome @ 2021-05-25 18:22:18
%%%