Prim
typedef pair <int, int> P;
int prim() {
int ans = 0, cnt = 0;
priority_queue <P, vector<P>, greater<P> > q;
fill(d + 1, d + n + 1, INF);
d[1] = 0;
q.push(P(d[1], 1));
while(!q.empty() && cnt < n) {
int y = q.top().second;
q.pop();
if(vis[y]) continue;
vis[y] = 1;
cnt++;
ans += d[y];
for(int i = 0; i < v[y].size(); i++) {
int t = v[y][i].t, w = v[y][i].w;
if(w < d[t]) {
d[t] = w;
q.push(P(d[t], t));
}
}
}
if(cnt < n) ans = -1;
return ans;
}
tarjan(缩点)
int dfn[M], low[M], z;
int col[M], c;
int st[M], it;
bool vis[M];
void tarjan(int i) {
z++;
dfn[i] = low[i] = z;
it++;
st[it] = i;
vis[i] = 1;
for(int j = 0; j < v[i].size(); j++) {
int t = v[i][j];
if(!dfn[t]) {
tarjan(t);
low[i] = min(low[i], low[t]);
} else if(vis[t]) {
low[i] = min(low[i], dfn[t]);
}
}
if(low[i] == dfn[i]) {
c++;
while(st[it] != i) {
col[st[it]] = cc;
vis[st[it]] = 0;
it--;
}
col[i] = c;
vis[i] = 0;
it--;
}
}
Dinic
void add(int f, int t, int w) {
v[f].push_back({t, w, (int)v[t].size()});
v[t].push_back({f, 0, (int)v[f].size() - 1});
}
void bfs() {
for(int i = st; i <= ed; i++) l[i] = -1;
queue <int> q;
l[st] = 0;
q.push(st);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i = 0; i < v[x].size(); i++) {
int t = v[x][i].t, w = v[x][i].w;
if(w > 0 && l[t] < 0) {
l[t] = l[x] + 1;
q.push(t);
}
}
}
}
int dinic(int i, int fl) {
if(i == ed) return fl;
for(; it[i] < v[i].size(); it[i]++) {
int t = v[i][it[i]].t, w = v[i][it[i]].w, r = v[i][it[i]].r;
if(w > 0 && l[t] > l[i]) {
int d = dinic(t, min(fl, w));
if(d > 0) {
v[i][it[i]].w -= d;
v[t][r].w += d;
return d;
}
}
}
return 0;
}
int main() {
//...
int flow = 0;
for(;;) {
bfs();
if(l[ed] < 0) break;
for(int i = st; i <= ed; i++) {
it[i] = 0;
}
for(;;) {
int f = dinic(st, MAX);
if(f <= 0) break;
flow += f;
}
}
return 0;
}
min_cost_flow (Primal-Dual)
void add(int f, int t, int w, int c) {
v[f].push_back({t, w, c, (int)v[t].size()});
v[t].push_back({f, 0, -c, (int)v[f].size() - 1});
}
int h[N], d[N], pre[N], id[N];
bool vis[N];
void spfa() {
queue<int> q;
fill(h, h + ed + 1, INF);
h[st] = 0, vis[st] = 1;
q.push(st);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 0; i < v[x].size(); i++) {
int t = v[x][i].t, w = v[x][i].w, c = v[x][i].c;
if(w > 0 && h[t] > h[x] + c) {
h[t] = h[x] + c;
if(!vis[t]) {
vis[t] = 1;
q.push(t);
}
}
}
}
}
void dijkstra() {
fill(d + 1, d + ed + 1, INF);
d[st] = 0;
priority_queue <P, vector<P>, greater<P> > q;
q.push(P(d[st], st));
while(!q.empty()) {
int x = q.top().first, y = q.top().second;
q.pop();
if(d[y] < x) continue;
for(int i = 0; i < v[y].size(); i++) {
int t = v[y][i].t, w = v[y][i].w, c = v[y][i].c;
if(w > 0 && d[t] > d[y] + c + h[y] - h[t]) {
d[t] = d[y] + c + h[y] - h[t];
pre[t] = y;
id[t] = i;
q.push(P(d[t], t));
}
}
}
}
int ans, flow;
void mcf() {
while(flow > 0) {
dijkstra();
for(int i = st; i <= ed; i++) {
h[i] += d[i];
}
int f = flow;
for(int i = ed; i != st; i = pre[i]) {
f = min(f, v[pre[i]][id[i]].w);
}
flow -= f;
ans += f * h[ed];
for(int i = ed; i != st; i = pre[i]) {
edge &e = v[pre[i]][id[i]];
e.w -= f;
v[i][e.r].w += f;
}
}
// 最小费用最大流:d[i] == INF返回
}
标签:图论,int,++,st,vis,push,板子,size
From: https://www.cnblogs.com/meowqwq/p/18401486