qip101 @ 2022-12-31 12:30:44
#include <bits/stdc++.h>
#define MAXN 100100
#define MAXM 2023
#define INF 2147483647
using namespace std;
long long n,m,s,t,ans;
long long dis[MAXM];
struct edge{
int v,w;
};
vector <edge> G[MAXN];
inline void add_edge(int u,int v,int w)
{
G[u].push_back((edge){v,w});
G[v].push_back((edge){u,0});
}
inline bool BFS()
{
memset(dis,INF,sizeof(dis));
queue <int> q;
q.push(s);
dis[s]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0;i<G[x].size();i++)
{
int to=G[x][i].v;
if(G[x][i].w>0 && dis[to]==INF)
{
q.push(to);
dis[to]=dis[x]+1;
if(to==t)
return true;
}
}
}
return false;
}
int DFS(int x,int sum)
{
if(x==t)
return sum;
long long k,res=0;
for(int i=0;i<G[x].size();i++)
{
int to=G[x][i].v;
if(G[x][i].w>0 && dis[to]==dis[x]+1)
{
k=DFS(to,min(sum,G[x][i].w));
if(k==0)
dis[to]=INF;
G[x][i].w-=k;
G[x][i].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
void Dinic()
{
while(BFS()==true)
ans+=DFS(s,INF);
}
int main()
{
//freopen("Dinic.in","r",stdin);
//freopen("Dinic.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> s >> t;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin >> u >> v >> w;
add_edge(u,v,w);
}
Dinic();
cout << ans << endl;
return 0;
}
by 方123456 @ 2022-12-31 12:49:59
@死在水中的鱼 网络流的反向边和正向边咋一样呀 /fad
if(k==0)
dis[to]=INF;
G[x][i].w-=k;
G[x][i].w+=k;
res+=k;
sum-=k;
这里的 G[x][i].w
真的有实质改变么?
by char_cha_ch @ 2022-12-31 12:52:23
@死在水中的鱼 宁哪来的反边啊。要不邻接矩阵,要不就前向星。
by qip101 @ 2022-12-31 12:56:36
@方123456 应该怎么写哦?
by liangbowen @ 2022-12-31 13:46:24
@死在水中的鱼 应该是
G[x][i].w-=k;
G[反边].w+=k;
链式前向星里,反边就是 i ^ 1
,vector就很难存。
可以再额外开一个数组,记录每条边的反边。不过还是 链前 方便(
by qip101 @ 2023-01-01 12:19:40
@liangbowen 反边应该就是G[i][x]?我改了以后还是输出0
by ssilrrr @ 2023-01-04 12:58:00
vector可以存边的指针。
而且,可以用map,但是带log。