现在的位置: 首页 > 综合 > 正文

poj 3459 Dual Core CPU(最小割 di…

2018年03月17日 ⁄ 综合 ⁄ 共 1299字 ⁄ 字号 评论关闭
现在做题 越做心越虚了。。。poj <wbr>3459 <wbr>Dual <wbr>Core <wbr>CPU(最小割 <wbr>dinic)
不能真正理解模版每一句的含意 根本就无法谈优化 都是加人的。我只是站在别人的肩膀上而已

题意:现在有n个任务,两个机器A和B,每个任务要么在A上完成,要么在B上完成,而且知道每个任务在A和B机器上完成所需要的费用。然后再给m行,每行
a,b,w三个数字。表示如果a任务和b任务不在同一个机器上工作的话,需要额外花费w。现在要求出完成所有任务最小的花费是多少。

思路:本来是想用stoer_wagner 做的 但。。。我不懂如何让它求出源点,和汇点分开的两个割集
所以改用dinic 求最大流 都是模版的力量,我也没什么好说的

8064K   
3079MS

#include <stdio.h>
#include <string.h>
#define VM 20005
#define EM 500000
#define inf 0x3f3f3f3f
struct E
{
    int
frm,to,cap,next;
}edge[EM];
int head[VM],dep[VM],p = 0;
int src,des;
void addedge (int cu,int cv,int cw,int rw) 
//无向边的逆边 cap = cw,有向边的cap = 0;
{
    edge[p].frm
= cu;
    edge[p].to =
cv;
    edge[p].cap
= cw;
    edge[p].next
= head[cu];
    head[cu] = p
++;
    edge[p].frm
= cv;
    edge[p].to =
cu;
    edge[p].cap
= rw;
    edge[p].next
= head[cv];
    head[cv] = p
++;
}

int BFS ()
{
    int
que[VM],i,front = 0,rear = 0;
    memset
(dep,-1,sizeof(dep));
    que[rear++]
= src;
    dep[src] =
0;
    while (front
!= rear)
    {
       
int u = que[front++];
       
front = front % VM;
       
for (i = head[u];i != -1;i = edge[i].next)
       
{
           
int v = edge[i].to;
           
if (edge[i].cap >
0&&dep[v] == -1)
           
{
               
dep[v] = dep[u] + 1;
               
que[rear++] = v;
               
rear = rear%VM;
               
if (v == des)
                   
return 1;
           
}
       
}
    }
    return
0;
}

int dinic ()
{
    int
i,top,res = 0;
    int
stack[VM],cur[VM];
    while
(BFS())
    {
       
memcpy(cur,head,sizeof(head));
       
int u = src;
    

抱歉!评论已关闭.