最大流 EK dinic sap
pku3281 Dining题目分析：有N头牛，F种食物，D种饮料，要求给每头牛分配一份食物和一种饮料，每种食物和每种饮料只能供一头牛享用，问最多能满足多少头牛的需要。
建图：建一超级源点标号为0，连上所有的食物，边权为1，建一超级汇点标号为2 * N + F + D + 1,连上所有的饮料，边权为1，在构造N个点和N头牛一一对应，保证每头牛只享用一种食物和一种饮料，边权为1，每头牛享用的食物和对应的构造点相连，边权为1，N头牛在和他喜欢的饮料相连，边权为1。
数据量小，用EK写了下：跑了170多ms
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0xfffffff
#define NN 410
int S, T;
int c;
int pre;
int bfs()
{
int que;
int mark;
memset(mark, 0, sizeof(mark));
que = S;
mark = 1;
int tail,head, u, i;
tail = head = 0;
while(head <= tail){
u = que;
for (i = 0; i <= T; i++){
if (!mark && c > 0){
mark = 1;
que[++tail] = i;
pre = u;
if (i == T){
return 1;
}
}
}
}
return 0;
}
void EK()
{
int minf, t;
int maxFlow = 0;
while(bfs()){
minf = INF;
t = T;
while(t != S){
if (c] < minf){
minf = c];
}
t = pre;
}
maxFlow += minf;
t = T;
while(t != S){
c] -= minf;
c] += minf;
t = pre;
}
}
printf("%d\n", maxFlow);
}
int main()
{
int i, j, a, b, d, f, N, F, D;
scanf("%d%d%d", &N, &F, &D);
S = 0;
T = 2 * N + F + D + 1;
memset(c, 0, sizeof(c));
for (i = 1; i <= F; i++){
c = 1;
}
for (i = 1; i <= D; i++){
c = 1;
}
for (i = 1; i <= N; i++){
scanf("%d%d", &f, &d);
for (j = 1; j <= f; j++){
scanf("%d", &a);
c = 1;
}
c = 1;
for (j = 1; j <= d; j++){
scanf("%d", &b);
c = 1;
}
}
EK();
//system("pause");
return 0;
}
昨天刚看dinic，熟悉一下代码，又写了一个dinic的，用的单路增广dfs：0ms
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0xfffffff
#define MM 60500
#define NN 410
int S, T, idx;
typedef struct node{
int v, wt;
struct node *nxt;
}NODE;
NODE edg;
NODE *link;
int h;
int que;
int Min(int a, int b){
return a < b ? a : b;
}
void add(int u, int v, int x, int y){
edg.v = v;
edg.wt = x;
edg.nxt = link;
link = edg + idx;
idx++;
edg.v = u;
edg.wt = y;
edg.nxt = link;
link = edg + idx;
idx++;
}
int bfs()
{
int u, v, w, tail, head;
memset(h, -1, sizeof(h));
que = S;
h = 0;
tail = head = 0;
while (head <= tail){
u = que;
for (NODE *p = link; p; p = p->nxt){
v = p->v;
w = p->wt;
if (h == -1 && w > 0){
h = h + 1;
que[++tail] = v;
}
}
}
return h != -1;
}
int dfs(int u, int flow){
if (u == T){
return flow;
}
int tmpf = 0;
int v, w, f;
for (NODE *p = link; p; p = p->nxt){
v = p->v;
w = p->wt;
if (h == h + 1 && w && tmpf < flow &&(f = dfs(v, Min(w, flow - tmpf)))){
p->wt -= f;
int t = p - edg;
if (t % 2 == 0){
edg.wt += f;
}else{
edg.wt += f;
}
tmpf += f;
}
}
if (tmpf == 0) h = -1;
return tmpf;
}
void dinic()
{
int ans = 0;
while(bfs()){
ans += dfs(S, INF);
}
printf("%d\n", ans);
}
int main()
{
int i, j, a, b, d, f, N, F, D;
scanf("%d%d%d", &N, &F, &D);
S = 0;
T = 2 * N + F + D + 1;
idx = 0;
for (i = S; i <= T; i++) link = 0;
for (i = 1; i <= F; i++){
add(0, 2 * N + i, 1, 0);
}
for (i = 1; i <= D; i++){
add(2 * N + F + i, T, 1, 0);
}
for (i = 1; i <= N; i++){
scanf("%d%d", &f, &d);
for (j = 1; j <= f; j++){
scanf("%d", &a);
add(2 * N + a, N + i, 1, 0);
}
//刚开始把这个写到里面去了，用EK的时候邻接矩阵存的，没影响，
//后来用了dinic，邻接表一存，多加了好多遍，WA了好多次
add(N + i, i, 1, 0);
for (j = 1; j <= d; j++){
scanf("%d", &b);
add(i, 2 * N + F + b, 1, 0);
}
}
dinic();
return 0;
}
正在学sap，就找了道题练了练，发现sap如果用递归形式写，真是太简单了。得感谢大牛：zkw
poj1459 Power Network
代码
#include<string.h>
#include<stdio.h>
#define INF 0xfffffff
#define MM 20500
#define NN 110
int S, T, idx;
typedef struct node{
int v, wt;
struct node *nxt;
}NODE;
NODE edg;
NODE *link;
int h;
int que;
int num;
int Min(int a, int b){
return a < b ? a : b;
}
/*加出边邻接表*/
void add(int u, int v, int x, int y){
/*正向加边*/
edg.v = v;
edg.wt = x;
edg.nxt = link;
link = edg + idx++;
/*反向加边*/
edg.v = u;
edg.wt = y;
edg.nxt = link;
link = edg + idx++;
}
int dfs(int u, int flow){
if (u == T){
return flow;
}
int v, w, f;
int tmp = T;
int tf = flow;
for (NODE *p = link; p; p = p->nxt){
v = p->v;
w = p->wt;
if (h == h + 1 && w){
f = dfs(v, Min(w, tf));
tf -= f;
p->wt -= f;
int t = p - edg;
if (t % 2 == 0){
edg.wt += f;
}else{
edg.wt += f;
}
if (!tf || h == T + 1) return flow - tf;
}
// 这里要取的是《有剩余容量的边中》的距离标号的最小值
if (h < tmp && p->wt > 0) tmp = h;
}
if (!(--num])) h = T + 1;
else num = tmp + 1]++;
return flow - tf;
}
void sap()
{
int ans = 0;
while (h <T + 1){
ans += dfs(S, INF);
}
printf("%d\n", ans);
}
int main()
{
int n, np, nc, m, a, b, d;
while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF){
S = n;//构造一个源点
T = n + 1;//构造一个汇点
idx = 0;
memset(link, 0, sizeof(link));
while (m--){
scanf(" (%d,%d)%d", &a, &b, &d);
if (a == b) continue;
add(a, b, d, 0);
}
while (np--){
scanf(" (%d)%d", &a, &d);
add(S, a, d, 0);
}
while (nc--){
scanf(" (%d)%d", &a, &d);
add(a, T, d, 0);
}
memset(h, 0, sizeof(h));
memset(num, 0, sizeof(num));
sap();
}
return 0;
}
页:
[1]