POJ3469Dual Core CPU

题意：给你n个模块，每个模块在A核花费为ai,在B核跑花费为bi,然后由m个任务（ai,bi,wi），表示如果ai,bi不在同一个核上跑，额外的花费为wi，求最小的花费。

分析：用最小的费用将对象划分成两个集合的问题，常常可以转化成最小割后解决，这题就是一道经典的问题；

1.考虑把N个模块按照在那个核执行分成两个集合。在A执行为集合S，B为T。

2.当模块属于A集的时候，花费为ai，所以就从向t连一条ai的边，而当模块属于B集的时候，花费为bi，所以就由s连一条向bi的边。然后对于每个任务，当ai,bi不同的时候花费为mi，所以就由ai,bi连两条容量为wi的边，跑一下最大流就可以得出对应的最小花费了

3.为什么会想到这些呢？首先来了解下：最小割，就是在流向图上去掉数量最少容量最小的边，使这个图变得不连通，源点s无法到达汇点t，这些边组成的容量就是最小割。那我们是不是可以想到，与最小费用进行对比，如果我们建的图是满足最小割为答案的话，那我们就可以很容易解决问题了；

4. 大佬文献

代码：

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cmath>

#include<queue>

#define ll long long

#define maxn 23500

#define maxe 1000000

#define inf 1100000000

using namespace std;

struct Edge

{

    int u, v, cap;

    int nxt;

}edge[maxe];

int head[maxn];

int n, m;

struct Dicnic

{

    int level[maxn];

    int iter[maxn];

    int add;

    void init(){

        add = ; memset(head, -, sizeof(head));

        memset(iter, -, sizeof(iter));

    }

    void insert(int u, int v, int c){

        edge[add].u = u; edge[add].v = v; edge[add].cap = c;

        edge[add].nxt = head[u]; head[u] = add++;

        edge[add].u = v; edge[add].v = u; edge[add].cap = ;

        edge[add].nxt = head[v]; head[v] = add++;

    }

    void bfs(int s){

        memset(level, -, sizeof(level));

        queue<int> que;

        level[s] = ;

        que.push(s);

        while (!que.empty()){

            int v = que.front(); que.pop();

            for (int i = head[v]; i != -; i = edge[i].nxt){

                Edge &e = edge[i];

                if (e.cap >  && level[e.v] < ){

                    level[e.v] = level[v] + ;

                    que.push(e.v);

                }

            }

        }

    }

    int dfs(int v, int t, int f){

        if (v == t) return f;

        for (int &i = iter[v]; i != -; i = edge[i].nxt){

            Edge &e = edge[i]; Edge &reve = edge[i ^ ];

            if (e.cap >  && level[v] < level[e.v]){

                int d = dfs(e.v, t, min(f, e.cap));

                if (d>){

                    e.cap -= d; reve.cap += d;

                    return d;

                }

            }

        }

        return ;

    }

    int max_flow(int s, int t){

        int flow = ;

        for (;;){

            bfs(s);

            if (level[t] < ) return flow;

            memcpy(iter, head, sizeof(iter));

            int f;

            while ((f = dfs(s, t, inf))>){

                flow += f;

            }

        }

    }

}net;

int a[maxn], b[maxn];

int main()

{

    while (cin >> n >> m){

        net.init();

        int s = , t = n + ;

        for (int i = ; i <= n; i++) {

            scanf("%d", a + i); scanf("%d", b + i);

            net.insert(i, t, a[i]);

            net.insert(s, i, b[i]);

        }

        int ui, vi, wi;

        for (int i = ; i < m; i++){

            scanf("%d%d%d", &ui, &vi, &wi);

            net.insert(ui, vi, wi);

            net.insert(vi, ui, wi);

        }

        printf("%d\n", net.max_flow(s,t));

    }

    return ;

}

巴特西

POJ3469Dual Core CPU

最新文章

热门文章