不能真正理解模版每一句的含意 根本就无法谈优化 都是加人的。我只是站在别人的肩膀上而已
题意:现在有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
{
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;
{
= cu;
cv;
= cw;
= head[cu];
++;
= cv;
cu;
= rw;
= head[cv];
++;
}
int BFS ()
{
que[VM],i,front = 0,rear = 0;
(dep,-1,sizeof(dep));
= src;
0;
!= 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;
}
}
0;
}
int dinic ()
{
i,top,res = 0;
stack[VM],cur[VM];
(BFS())
memcpy(cur,head,sizeof(head));
int u = src;