POJ 3469 Dual Core CPU（最小割模型的建立）

分析：

这类问题的一遍描述，把一些对象分成两组，划分有一些代价，问最小代价。一般性的思路是，

把这两组看成是S点和T点，把划分的代价和割边的容量对应起来求最小割。

把S和可模版tem之间到达关系看作是属于核A，对称地，T对应B。模块tem安装在A上代价A_i，就是割断tem和T，连一条tem到T的容量为A_i的边。

相应地，对于B_i,连一条S到tem容量为B_i的边。当a_i安装在A上，b_i安装在B上，也就是s - a_i， b_i - t（-表示可到达），这时候如果有额外花费w_i

那么a_i - b_i之间连上容量为w_i的边，反过来b_i和a_i对换一下也是类似的。

输入很大，光是I/O就能优化1s，ISAP会更快。

/*********************************************************

*            ------------------                          *

*   author AbyssalFish                                   *

**********************************************************/

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxv = 2e4+, maxe = 4e5+maxv*;

int hd[maxv],to[maxe],nx[maxe],ec,cap[maxe];

#define eachEage int i = hd[u]; ~i; i = nx[i]

inline void add(int u,int v, int cp)

{

    nx[ec] = hd[u];

    to[ec] = v;

    cap[ec] = cp;

    hd[u] = ec++;

}

inline void Add(int u,int v,int cp)

{

    add(u,v,cp); add(v,u,);

}

int lv[maxv], q[maxv];

bool vis[maxv];

int S,T;

bool bfs()

{

    memset(vis,,sizeof(bool)*(T+));

    int l = , r = ;

    lv[q[r++] = S] = ;

    vis[S] = true;

    while(l<r){

        int u = q[l++];

        for(eachEage){

            int v = to[i];

            if(!vis[v] && cap[i]){

                lv[q[r++] = v] = lv[u] + ;

                vis[v] = true;

            }

        }

    }

    return vis[T];

}

int cur[maxv];

int aug(int u,int a)

{

    if(u == T || !a) return a;

    int flow = ,f;

    for(int &i = cur[u]; ~i; i = nx[i]){

        int v = to[i];

        if(lv[v] == lv[u]+ && (f = aug(v, min(a,cap[i])))){

            flow += f; a -= f;

            cap[i] -= f; cap[i^] += f;

            if(!a) break;

        }

    }

    return flow;

}

int maxFlow()

{

    int flow = ;

    while(bfs()){

        memcpy(cur,hd,sizeof(int)*(T+));

        flow += aug(S,<<);

    }

    return flow;

}

inline int read()

{

    int ret; char c; while(c = getchar(),c<''||c>'');

    ret = c-'';

    while(c = getchar(),c>=''&&c<='') ret = ret* + c-'';

    return ret;

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int n, m;

    while(~scanf("%d%d",&n,&m)){

        S = ; T = n+;

        memset(hd,0xff,sizeof(int)*(T+)); ec = ;

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

            Add(i,T,read());

            Add(S,i,read());

        }

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

            int a = read(),b = read(),w = read();

            add(a,b,w); add(b,a,w);

        }

        printf("%d\n",maxFlow());

    }

    return ;

}

巴特西

POJ 3469 Dual Core CPU（最小割模型的建立）

最新文章

热门文章