RT,本蒟蒻不理解这坨屎山发生了什么
P.S.:因为费用流板子题还询问别的,所以就不放那里了,请放过这个蒟蒻
class Min_Cost_Flow_Graph{
private:
struct Flow_Edge{
int v, cap, cost, id;
};
vector<Flow_Edge> gv[501];
int n, tot;
int curr[501], dis[501], vis[501], flow[30001], mp[30001];
int source, sink;
public:
void add_edge(int u, int v, int w, int x){
Flow_Edge k; k.v = v, k.cap = w, k.cost = x, k.id = ++tot;
gv[u].pb(k); mp[tot] = gv[u].size() - 1;
flow[tot] = w;
k.v = u, k.cap = 0LL, k.cost = -x, k.id = ++tot;
gv[v].pb(k); mp[tot] = gv[v].size() - 1;
flow[tot] = 0LL;
}
void init(int k, int sc, int sk){
n = k, source = sc, sink = sk;
rep(i, 1, n, 1)
gv[i].clear(), curr[i] = 0LL, mp[i] = 0LL;
tot = -1;
}
bool spfa(){
rep(i, 1, n, 1)
vis[i] = 0LL, dis[i] = MAXN;
qi q; q.push(source);
dis[source] = 0LL;
while(!q.empty()){
int x = q.front(); q.pop();
vis[x] = 0;
repn(i, 0, gv[x].size(), 1){
Flow_Edge u = gv[x][i];
int y = u.v, z = u.cost;
if(u.cap > 0 && dis[y] > dis[x] + z){
dis[y] = dis[x] + z;
if(!vis[y])
vis[y] = 1, q.push(y);
}
}
}
return (dis[sink] <= INT_MAX);
}
int dfs(int x, int fl){
if(x == sink) return fl;
int ans = 0;
vis[x] = 1;
int i = curr[x];
while(i < gv[x].size()){
curr[x] = i;
Flow_Edge y = gv[x][i];
i++; int tmp;
if(y.cap <= 0 || dis[y.v] != dis[x] + y.cost || vis[y.v]){
continue;
}
if((tmp = dfs(y.v, min(fl - ans, y.cap))) > 0){
gv[x][mp[y.id]].cap -= tmp;
gv[y.v][mp[y.id ^ 1]].cap += tmp;
ans += tmp;
}
if(ans >= fl) break;
}
return ans;
}
int Min_Cost_Max_Flow(){
int fl; int ans = 0;
while(spfa()){
rep(i, 1, n, 1) curr[i] = 0LL;
while(1){
int fl = dfs(source, MAXN);
if(fl == 0) break;
rep(i, 1, n, 1) vis[i] = 0LL;
}
}
rep(i, 1, n, 1){
repn(j, 0, gv[i].size(), 1){
Flow_Edge x = gv[i][j];
ans += x.cost * (flow[x.id] - x.cap);
}
}
return ans;
}
};