程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3422 最小費用最大流 zkw或者普通版本

POJ 3422 最小費用最大流 zkw或者普通版本

編輯:C++入門知識

建圖的話

每個點拆成兩個點u, u',連一條容量為1費用為金幣數的邊,再連一條容量為k,費用為0的邊

然後每個點和他右邊或者下邊的點連邊 i'->j這樣連

然後源點連1點,右下角那個點去連匯點,容量都為k,費用為0

普通寫法


[cpp]
#include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <string>  
#include <cstdio>  
#include <cmath>  
#include <queue>  
#include <map>  
#include <set>  
#define eps 1e-5  
#define MAXN 5555  
#define MAXM 55555  
#define INF 100000007  
using namespace std; 
struct EDGE 

    int v, cap, cost, next, re;    //  re記錄逆邊的下標。  
} edge[MAXM]; 
int n, m, ans, flow, src, des; 
int e, head[MAXN]; 
int que[MAXN], pre[MAXN], dis[MAXN]; 
bool vis[MAXN]; 
void init() 

    e = ans = flow = 0; 
    memset(head, -1, sizeof(head)); 

void add(int u, int v, int cap, int cost) 

    edge[e].v = v; 
    edge[e].cap = cap; 
    edge[e].cost = cost; 
    edge[e].next = head[u]; 
    edge[e].re = e + 1; 
    head[u] = e++; 
    edge[e].v = u; 
    edge[e].cap = 0; 
    edge[e].cost = -cost; 
    edge[e].next = head[v]; 
    edge[e].re = e - 1; 
    head[v] = e++; 

bool spfa() 

    int i, h = 0, t = 1; 
    for(i = 0; i <= n; i ++) 
    { 
        dis[i] = INF; 
        vis[i] = false; 
    } 
    dis[src] = 0; 
    que[0] = src; 
    vis[src] = true; 
    while(t != h) 
    { 
        int u = que[h++]; 
        h %= n; 
        vis[u] = false; 
        for(i = head[u]; i != -1; i = edge[i].next) 
        { 
            int v = edge[i].v; 
            if(edge[i].cap && dis[v] > dis[u] + edge[i].cost) 
            { 
                dis[v] = dis[u] + edge[i].cost; 
                pre[v] = i; 
                if(!vis[v]) 
                { 
                    vis[v] = true; 
                    que[t++] = v; 
                    t %= n; 
                } 
            } 
        } 
    } 
    if(dis[des] == INF) return false; 
    return true; 

void end() 

    int u, p, mi = INF; 
    for(u = des; u != src; u = edge[edge[p].re].v) 
    { 
        p = pre[u]; 
        mi = min(mi, edge[p].cap); 
    } 
    for(u = des; u != src; u = edge[edge[p].re].v) 
    { 
        p = pre[u]; 
        edge[p].cap -= mi; 
        edge[edge[p].re].cap += mi; 
        ans += mi * edge[p].cost;     //  cost記錄的為單位流量費用,必須得乘以流量。  
    } 
    flow += mi; 

int nt, k; 
void build() 

    init(); 
    int w; 
    for(int i = 1; i <= nt; i++) 
        for(int j = 1; j <= nt; j++) 
        { 
            scanf("%d", &w); 
            int id = (i - 1) * nt + j; 
            add(id, id + nt * nt, 1, -w); 
            add(id, id + nt * nt, k, 0); 
            if(i < nt) add(id + nt * nt, id + nt, k, 0); 
            if(j < nt) add(id + nt * nt, id + 1, k, 0); 
        } 
    src = nt * nt * 2 + 1; 
    des = nt * nt * 2 + 2; 
    n = des; 
    add(src, 1, k, 0); 
    add(nt * nt * 2, des, k, 0); 

void MCMF() 

    init(); 
    build(); 
    while(spfa()) end(); 

int main() 

    while(scanf("%d%d", &nt, &k) != EOF) 
    { 
        MCMF(); 
        printf("%d\n", -ans); 
    } 
    return 0; 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 5555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
    int v, cap, cost, next, re;    //  re記錄逆邊的下標。
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{
    e = ans = flow = 0;
    memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{
    edge[e].v = v;
    edge[e].cap = cap;
    edge[e].cost = cost;
    edge[e].next = head[u];
    edge[e].re = e + 1;
    head[u] = e++;
    edge[e].v = u;
    edge[e].cap = 0;
    edge[e].cost = -cost;
    edge[e].next = head[v];
    edge[e].re = e - 1;
    head[v] = e++;
}
bool spfa()
{
    int i, h = 0, t = 1;
    for(i = 0; i <= n; i ++)
    {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[src] = 0;
    que[0] = src;
    vis[src] = true;
    while(t != h)
    {
        int u = que[h++];
        h %= n;
        vis[u] = false;
        for(i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(edge[i].cap && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    que[t++] = v;
                    t %= n;
                }
            }
        }
    }
    if(dis[des] == INF) return false;
    return true;
}
void end()
{
    int u, p, mi = INF;
    for(u = des; u != src; u = edge[edge[p].re].v)
    {
        p = pre[u];
        mi = min(mi, edge[p].cap);
    }
    for(u = des; u != src; u = edge[edge[p].re].v)
    {
        p = pre[u];
        edge[p].cap -= mi;
        edge[edge[p].re].cap += mi;
        ans += mi * edge[p].cost;     //  cost記錄的為單位流量費用,必須得乘以流量。
    }
    flow += mi;
}
int nt, k;
void build()
{
    init();
    int w;
    for(int i = 1; i <= nt; i++)
        for(int j = 1; j <= nt; j++)
        {
            scanf("%d", &w);
            int id = (i - 1) * nt + j;
            add(id, id + nt * nt, 1, -w);
            add(id, id + nt * nt, k, 0);
            if(i < nt) add(id + nt * nt, id + nt, k, 0);
            if(j < nt) add(id + nt * nt, id + 1, k, 0);
        }
    src = nt * nt * 2 + 1;
    des = nt * nt * 2 + 2;
    n = des;
    add(src, 1, k, 0);
    add(nt * nt * 2, des, k, 0);
}
void MCMF()
{
    init();
    build();
    while(spfa()) end();
}
int main()
{
    while(scanf("%d%d", &nt, &k) != EOF)
    {
        MCMF();
        printf("%d\n", -ans);
    }
    return 0;
}

 


zkw寫法

 


[cpp]
#include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <string>  
#include <cstdio>  
#include <cmath>  
#include <queue>  
#include <deque>  
#include <map>  
#include <set>  
#define eps 1e-5  
#define MAXN 5555  
#define MAXM 55555  
#define INF 100000007  
using namespace std; 
struct EDGE 

    int cost, cap, v; 
    int next, re; 
}edge[MAXM]; 
int head[MAXN], e; 
int vis[MAXN], d[MAXN]; 
int ans, cost, src, des, n; 
void init() 

    memset(head, -1, sizeof(head)); 
    e = 0; 
    ans = cost = 0; 

void add(int u, int v, int cap, int cost) 

    edge[e].v = v; 
    edge[e].cap = cap; 
    edge[e].cost = cost; 
    edge[e].re = e + 1; 
    edge[e].next = head[u]; 
    head[u] = e++; 
    edge[e].v = u; 
    edge[e].cap = 0; 
    edge[e].cost = -cost; 
    edge[e].re = e - 1; 
    edge[e].next = head[v]; 
    head[v] = e++; 

int aug(int u, int f) 

    if(u == des) 
    { 
        ans += cost * f; 
        return f; 
    } 
    vis[u] = 1; 
    int tmp = f; 
    for(int i = head[u]; i != -1; i = edge[i].next) 
        if(edge[i].cap && !edge[i].cost && !vis[edge[i].v]) 
        { 
            int delta = aug(edge[i].v, tmp < edge[i].cap ? tmp : edge[i].cap); 
            edge[i].cap -= delta; 
            edge[edge[i].re].cap += delta; 
            tmp -= delta; 
            if(!tmp) return f; 
        } 
    return f - tmp; 

bool modlabel() 

    for(int i = 0; i <= n; i++) d[i] = INF; 
    d[des] = 0; 
    deque<int>Q; 
    Q.push_back(des); 
    while(!Q.empty()) 
    { 
        int u = Q.front(), tmp; 
        Q.pop_front(); 
        for(int i = head[u]; i != -1; i = edge[i].next) 
            if(edge[edge[i].re].cap && (tmp = d[u] - edge[i].cost) < d[edge[i].v]) 
                (d[edge[i].v] = tmp) <= d[Q.empty() ? src : Q.front()] ? Q.push_front(edge[i].v) : Q.push_back(edge[i].v); 
    } 
    for(int u = 1; u <= n; u++) 
        for(int i = head[u]; i != -1; i = edge[i].next) 
            edge[i].cost += d[edge[i].v] - d[u]; 
    cost += d[src]; 
    return d[src] < INF; 

void costflow() 

    while(modlabel()) 
    { 
        do 
        { 
            memset(vis, 0, sizeof(vis)); 
        }while(aug(src, INF)); 
    } 

int nt, k; 
int main() 

    int w; 
    while(scanf("%d%d", &nt, &k) != EOF) 
    { 
        init(); 
        for(int i = 1; i <= nt; i++) 
            for(int j = 1; j <= nt; j++) 
            { 
                scanf("%d", &w); 
                int id = (i - 1) * nt + j; 
                add(id, id + nt * nt, 1, -w); 
                add(id, id + nt * nt, k, 0); 
                if(i < nt) add(id + nt * nt, id + nt, k, 0); 
                if(j < nt) add(id + nt * nt, id + 1, k, 0); 
            } 
        src = nt * nt * 2 + 1; 
        des = nt * nt * 2 + 2; 
        n = des; 
        add(src, 1, k, 0); 
        add(nt * nt * 2, des, k, 0); 
        costflow(); 
        printf("%d\n", -ans); 
    } 
    return 0; 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 5555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
    int cost, cap, v;
    int next, re;
}edge[MAXM];
int head[MAXN], e;
int vis[MAXN], d[MAXN];
int ans, cost, src, des, n;
void init()
{
    memset(head, -1, sizeof(head));
    e = 0;
    ans = cost = 0;
}
void add(int u, int v, int cap, int cost)
{
    edge[e].v = v;
    edge[e].cap = cap;
    edge[e].cost = cost;
    edge[e].re = e + 1;
    edge[e].next = head[u];
    head[u] = e++;
    edge[e].v = u;
    edge[e].cap = 0;
    edge[e].cost = -cost;
    edge[e].re = e - 1;
    edge[e].next = head[v];
    head[v] = e++;
}
int aug(int u, int f)
{
    if(u == des)
    {
        ans += cost * f;
        return f;
    }
    vis[u] = 1;
    int tmp = f;
    for(int i = head[u]; i != -1; i = edge[i].next)
        if(edge[i].cap && !edge[i].cost && !vis[edge[i].v])
        {
            int delta = aug(edge[i].v, tmp < edge[i].cap ? tmp : edge[i].cap);
            edge[i].cap -= delta;
            edge[edge[i].re].cap += delta;
            tmp -= delta;
            if(!tmp) return f;
        }
    return f - tmp;
}
bool modlabel()
{
    for(int i = 0; i <= n; i++) d[i] = INF;
    d[des] = 0;
    deque<int>Q;
    Q.push_back(des);
    while(!Q.empty())
    {
        int u = Q.front(), tmp;
        Q.pop_front();
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[edge[i].re].cap && (tmp = d[u] - edge[i].cost) < d[edge[i].v])
                (d[edge[i].v] = tmp) <= d[Q.empty() ? src : Q.front()] ? Q.push_front(edge[i].v) : Q.push_back(edge[i].v);
    }
    for(int u = 1; u <= n; u++)
        for(int i = head[u]; i != -1; i = edge[i].next)
            edge[i].cost += d[edge[i].v] - d[u];
    cost += d[src];
    return d[src] < INF;
}
void costflow()
{
    while(modlabel())
    {
        do
        {
            memset(vis, 0, sizeof(vis));
        }while(aug(src, INF));
    }
}
int nt, k;
int main()
{
    int w;
    while(scanf("%d%d", &nt, &k) != EOF)
    {
        init();
        for(int i = 1; i <= nt; i++)
            for(int j = 1; j <= nt; j++)
            {
                scanf("%d", &w);
                int id = (i - 1) * nt + j;
                add(id, id + nt * nt, 1, -w);
                add(id, id + nt * nt, k, 0);
                if(i < nt) add(id + nt * nt, id + nt, k, 0);
                if(j < nt) add(id + nt * nt, id + 1, k, 0);
            }
        src = nt * nt * 2 + 1;
        des = nt * nt * 2 + 2;
        n = des;
        add(src, 1, k, 0);
        add(nt * nt * 2, des, k, 0);
        costflow();
        printf("%d\n", -ans);
    }
    return 0;
}

 作者:sdj222555
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved