最小费用最大流
#include<iostream>
using namespace std;
struct edge
{
int u, v, next, f, w;
}e[40000001];
int n, m;
int mincost;
int p[200000];
int head[200000];
int num;
int s, t;
int max_flow;
void add(int s, int t, int w, int c)
{
e[num].f = c;
e[num].next = head[s];
head[s] = num;
e[num].u = s;
e[num].v = t;
e[num++].w = w;
return ;
}
void addedge(int s, int t, int w, int c)
{
add(s, t, w, c);
add(t, s, -w, 0);
return ;
}
int Q[200000]/*开大点*/,d[200000];
bool spfa()
{
int i, j;
int front = 0, tail = 0;
bool ok[200000] = {0};//注意不
for(i = 0; i <= t; i++)//t一般需要是最大的值，
{
d[i] = INT_MAX;
}
d[s] = 0;
ok[s] = 1;
p[s] = -1;
Q[++tail] = s;
while(tail! = front)
{ www.zzzyk.com
i = Q[++front];
ok[i] = 0;
for(j = head[i]; j != -1; j = e[j].next)
{
if(e[j].f > 0 && d[i] + e[j].w < d[e[j].v])
{
d[e[j].v] = d[i] + e[j].w;
p[e[j].v] = j;
if(!ok[e[j].v])
{
Q[++tail] = e[j].v;
ok[e[j].v] = 1;
}
}
}
}
if(d[t] < INT_MAX)
return 1;
else return 0;
}
int solve()
{
int i;
int minflow = INT_MAX;
for(i = p[t]; i != -1; i = p[e[i].u])
{
if(minflow > e[i].f)
minflow = e[i].f;
}
for (i = p[t]; i != -1; i = p[e[i].u])
{
e[i].f -= minflow;
e[i^1].f += minflow;
mincost += e[i].w*minflow;
}
max_flow += minflow;
return 0;
}
/*
int main()
{
memset(head, -1, sizeof(head));
num = 0;
s = 0;
t = n + 1;
max_flow = 0;
//如果有a->b的边，容量为w,单位费用为c则：
addedge(a, b, c, w);
mincost = 0;
while(spfa())
{
solve();
}
printf("%d\n",mincost);
}
return 0;
}
*/
void init()
{
memset(head, -1, sizeof(head));
num = 0;
// s=0;
// t=n+1;
max_flow = 0;
//如果有a->b的边，容量为w,单位费用为c则：
// addedge(a, b, c, w);
mincost=0;
}
补充：综合编程 , 其他综合 ,
