oval_m @ 2022-04-07 00:50:58
照着紫书打的,#11WA 手算了一下,找到了问题 但是不知道怎么改
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#define INF ((1uLL<<63)-1)
#define N 210
#define ll long long
using namespace std;
struct Edge
{
int from,to;
ll cap,flow; //边的 容量 和 流量
Edge(int fr,int t,ll ca,ll fl):from(fr),to(t),cap(ca),flow(fl){}
};
vector<Edge> edges; //边的数组
vector<int> g[N]; //图 g[i][j] 为 edges的下标 即 edges[g[i][j]]
ll a[N]; //a[i]表示 s到i的路径上的最小残量 起点到i的可改进量 同时a还可以作为bfs的vis数组
int p[N]; //最短路树上p的入边编号
int n,m,s,t; //节点数 边数 起点 终点 建图之后的总边数为原来的2倍(反向边)
void AddEdge(int u,int v,ll cap)
{
int m = edges.size();
edges.push_back(Edge(u,v,cap,0));
edges.push_back(Edge(v,u,0,0)); //反向边
//将正边和反边放一起 当正边为[j] 反边可以表示成 [j^1] 边的起点从0开始
g[u].push_back(m);
g[u].push_back(m+1);
}
ll EdmondsKarp()
{
ll flow = 0;
while(true) //貌似每次循环就是一次增广? //每次找一条最短路
{
memset(a,0,sizeof(a));
queue<int> q; //bfs
q.push(s); //起点
a[s] = INF; //起点的可改进量为无穷
while(!q.empty())
{
int temp = q.front();q.pop();
for(int i = 0; i < g[temp].size(); i++)
{
Edge& e = edges[g[temp][i]];
if(!a[e.to] && e.cap>e.flow) //该点没被访问过 && 这条边的流量还没有满
{
a[e.to] = min(a[temp],e.cap-e.flow); //可流向该点的流量为 起点有的和边剩余的流量 取最小值
p[e.to] = g[temp][i]; //记录 e.to这个节点在最短路中是由那条边走过来的
q.push(e.to);
}
}
if(a[t])break; //已经遍历到了终点 无需继续bfs
}
if(!a[t])break; //出口
//一下对edges数组的flow进行更改 为下次循环做准备
for(int i = t; i != s; i = edges[p[i]].from) //用p数组按照最短路回溯
{
edges[p[i]].flow += a[t];
edges[p[i]^1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
signed main()
{
cin >> n >> m >> s >> t;
for(int i = 0; i < m; i++)
{
int a,b;
ll cap;
cin >> a >> b >> cap;
AddEdge(a,b,cap);
}
cout << EdmondsKarp();
return 0;
}