金珂拉 @ 2021-02-08 11:42:49
rt\ 蒟蒻求教
by 金珂拉 @ 2021-02-08 11:43:29
#include<bits/stdc++.h>
using namespace std;
int const N=5003;
int const inf=0x7f7f7f7f;
struct node {
int v,nt;
long long c;
} e[520010];
long long top=1,h[N],n,m,s,t,ans,vis[N],f[N][N],d[N];
void add(int x,int y,int z)
{
e[++top].v=y;
e[top].c=z;
e[top].nt=h[x];
h[x]=top;
e[++top].v=x;
e[top].c=0;
e[top].nt=h[y];
h[y]=top;
}
int bfs()
{
queue<int> q;
q.push(s);
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=h[x];i;i=e[i].nt)
{
int v=e[i].v;
if(e[i].c && !vis[v])
{
d[v]=d[x]+1;
q.push(v);
vis[v]=1;
}
}
}
return vis[t];
}
int dfs(int x,int y)
{
if(x==t) return y;
int sum=0;
for(int i=h[x];i;i=e[i].nt)
{
int v=e[i].v;
if(d[v]==d[x]+1 && e[i].c!=0 && y<ans)
{
int det=dfs(v,min(e[i].c,y-ans));
e[v].c-=det;
e[v^1].c+=det;
ans+=det;
}
}
return ans;
}
void dinic()
{
while(bfs())
{
ans+=dfs(s,inf);
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(f[x][y]==0) {
add(x,y,z);
f[x][y]=top;
}
else {
e[f[x][y]-1].c+=z;
}
}
dinic();
cout<<ans;
}
就很奇妙的炸了
by zimujun @ 2021-02-08 11:45:54
@金铠磊
dinic 没加当前弧优化,虽然不是必要的但是会比较慢
dinic 搜索的过程中搜到没有流量的点没将其封锁
by 金珂拉 @ 2021-02-08 12:29:09
@zimujunqwq 我刚刚把最大边优化和点封锁都加上了,但是依旧炸了,十个点全部TLE…… 但是我下载下来的两个点全部都能跑而且时间都不超过时限的 是有什么操作卡评测了吗