费用流
程序员文章站
2022-05-22 14:57:32
...
const int inf = 0x3f3f3f3f;
struct mcmf{
int he[maxn],tot,edge[maxm],ne[maxm],ver[maxm],cost[maxm];
int pre[maxn],d[maxn];
bool vis[maxn];
int n;
void init(int x){
n = x;
tot = 1;
for( int i = 0;i <= n;i++ ) he[i] = 0;
}
void add(int x,int y,int cap,int c){
ver[++tot] = y;
ne[tot] = he[x];
he[x] = tot;
edge[tot] = cap;
cost[tot] = c;
ver[++tot] = x;
ne[tot] = he[y];
he[y] = tot;
edge[tot] = 0;
cost[tot] = -c;
}
bool spfa(int s,int t){
queue<int>q;
for(int i = 0;i < n;i++){
d[i] = inf;
vis[i] = false;
pre[i] = -1;
}
d[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = false;
for(int cure = he[x]; cure ;cure = ne[cure]){
int y = ver[cure];
if(edge[cure] && d[y] > d[x] + cost[cure] ){
d[y] = d[x] + cost[cure];
pre[y] = cure;
if(!vis[y]){
vis[y] = true;
q.push(y);
}
}
}
}
if(pre[t] == -1)return false;
else return true;
}
int mincost(int s,int t,int &cc){
int flow = 0;
cc = 0;
while(spfa(s,t)){
int mn = inf;
for(int cure = pre[t];cure != -1;cure = pre[ ver[cure^1] ]){
if(mn > edge[cure])
mn = edge[cure];
}
for(int cure = pre[t];cure != -1;cure = pre[ ver[cure^1] ]){
edge[cure] -= mn;
edge[cure^1] += mn;
cc += cost[cure] * mn;
}
flow += mn;
}
return flow;
}
} g;
上一篇: 王济给妹妹相中一个才貌双全的人,为何却被母亲坚决反对呢?
下一篇: 软文推广思路:思维及技巧