写前向星不好吗。。
by CmsMartin @ 2023-01-15 12:49:04
写前向星不好吗。。
by peaneevall_kalaa @ 2023-01-15 13:20:15
参考一下？
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
// const int 1e18 = 1e18;
#define int long long
int n, m, s, t;
int cur[maxn], dis[maxn];
int vis[maxn];
int psz = 1;
struct Edge{
int v, w, c, cp;
};
vector <Edge> g[maxn];
void add_edge(int u, int v, int w, int c){
Edge e1 = Edge{v, w, c, g[v].size()};
Edge e2 = Edge{u, 0, -c, g[u].size()};
g[u].push_back(e1);
g[v].push_back(e2);
}
bool spfa()
{
queue<int> q;
for(int i = 0; i < maxn; i++){
dis[i] = 1e18;
}
memset(vis, 0, sizeof(vis));
vis[s] = true;
dis[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop(); vis[u] = false;
int l = g[u].size();
for(int i = 0; i < l; i++)
{
int v = g[u][i].v, r = g[u][i].w, c = g[u][i].c;
if(r and dis[u] + c < dis[v]){
dis[v] = dis[u] + c;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
return dis[t] != 1e18;
}
int aug(int u, int l, int &cost){
if(u == t) return l;
vis[u] = true;
int f = 0;
for(int &i = cur[u]; i < g[u].size(); i++){
int v = g[u][i].v, r = g[u][i].w, c = g[u][i].c;
if(dis[v] != dis[u] + c or !r or vis[v]) continue;
int d = aug(v, min(r, l), cost);
g[u][i].w -= d;
g[v][g[u][i].cp].w += d;
f += d, l -= d;
cost += d*c;
if(!l) break;
}
vis[u] = false;
return f;
}
signed main(){
cin>>n>>m>>s>>t;
while(m--){
int u, v, w, c;
cin>>u>>v>>w>>c;
add_edge(u, v, w, c);
}
int flow = 0, ans = 0;
while(spfa()){
memset(cur, 0, sizeof(cur));
while(true){
int d = aug(s, 1e18, flow);
if(!d) break;
ans += d;
}
}
cout<<ans<<' '<<flow<<endl;
return 0;
}
```
by Champagne_Supernova @ 2023-01-15 13:21:41