POJ 3469 Dual Core CPU 最小割问题

链接：http://poj.org/problem?id=3469

题意：给出多个任务在两个处理器分别处理时的花费，给出一些条件有些任务在不同的处理器处理会有额外的花费，问最小的花费是多少。

思路：最小割问题。网络流算法不难，难的是建图。看到将图分成两部分的问题就要向最小割上去想。

本题建图：

1.源点和汇点分别是两个核。

2.弧长是模块在两个核各自的花费。

3.出现额外花费就将两个模块连接，弧长是额外花费，双向连接。

这样最小割就是最小花费了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#define PI acos(-1.0)
#define maxn 20010
#define maxm 200100
#define INF 0x7fffffff
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
struct Edge
{
    int v,w;
    int next;
}edge[maxn*50];
int head[maxn],dist[maxn],vis[maxn];
int top,src,sink;
int add_edge(int u,int v,int w)
{
    edge[top].v=v;
    edge[top].w=w;
    edge[top].next=head[u];
    head[u]=top++;
    edge[top].v=u;
    edge[top].w=w;
    edge[top].next=head[v];
    head[v]=top++;
}
int init()
{
    mem(head,-1);
    top=0;
}
queue<int>que;
void bfs()
{
    mem(dist,0);
    mem(vis,0);
    while(!que.empty())
        que.pop();
    vis[src]=1;
    que.push(src);
    while(!que.empty())
    {
        int t=que.front();
        que.pop();
        for(int i=head[t]; i!=-1; i=edge[i].next)
        {
            if(!vis[edge[i].v]&&edge[i].w)
            {
                que.push(edge[i].v);
                dist[edge[i].v]=dist[t]+1;
                vis[edge[i].v]=1;
            }
        }
    }
    return;
}
int dfs(int u,int del)
{
    if(u==sink)
        return del;
    int ret=0;
    for(int i=head[u]; del&&i!=-1; i=edge[i].next)
    {
        if(dist[edge[i].v]==dist[u]+1&&edge[i].w)
        {
            int d=dfs(edge[i].v,min(edge[i].w,del));
            edge[i].w-=d;
            edge[i^1].w+=d;
            del-=d;
            ret+=d;
        }
    }
    return ret;
}
int maxflow()
{
    int ans=0;
    while(1)
    {
        bfs();
        if(!vis[sink])
            return ans;
        ans+=dfs(src,INF);
    }
}
int main()
{
    int tot,tt;
    scanf("%d%d",&tot,&tt);
    src=0,sink=tot+1;
    init();
    for(int i=1;i<=tot;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add_edge(0,i,a);
        add_edge(i,tot+1,b);
    }
    for(int i=1;i<=tt;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    printf("%d\n",maxflow());
}

POJ 3469 Dual Core CPU 最小割问题,布布扣,bubuko.com

POJ 3469 Dual Core CPU 最小割问题

原文：http://blog.csdn.net/ooooooooe/article/details/20991097