POJ 3422 最小费用最大流 zkw或者普通版本 - c++编程基础

()
{
int w;
while(scanf("%d%d", &nt, &k) != EOF)
{
init();
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= nt; j++)
{
scanf("%d", &w);
int id = (i - 1) * nt + j;
add(id, id + nt * nt, 1, -w);
add(id, id + nt * nt, k, 0);
if(i < nt) add(id + nt * nt, id + nt, k, 0);
if(j < nt) add(id + nt * nt, id + 1, k, 0);
}
src = nt * nt * 2 + 1;
des = nt * nt * 2 + 2;
n = des;
add(src, 1, k, 0);
add(nt * nt * 2, des, k, 0);
costflow();
printf("%d\n", -ans);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 5555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
int cost, cap, v;
int next, re;
}edge[MAXM];
int head[MAXN], e;
int vis[MAXN], d[MAXN];
int ans, cost, src, des, n;
void init()
{
memset(head, -1, sizeof(head));
e = 0;
ans = cost = 0;
}
void add(int u, int v, int cap, int cost)
{
edge[e].v = v;
edge[e].cap = cap;
edge[e].cost = cost;
edge[e].re = e + 1;
edge[e].next = head[u];
head[u] = e++;
edge[e].v = u;
edge[e].cap = 0;
edge[e].cost = -cost;
edge[e].re = e - 1;
edge[e].next = head[v];
head[v] = e++;
}
int aug(int u, int f)
{
if(u == des)
{
ans += cost * f;

return f;
}
vis[u] = 1;
int tmp = f;
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[i].cap && !edge[i].cost && !vis[edge[i].v])
{
int delta = aug(edge[i].v, tmp < edge[i].cap tmp : edge[i].cap);
edge[i].cap -= delta;
edge[edge[i].re].cap += delta;
tmp -= delta;
if(!tmp) return f;
}
return f - tmp;
}
bool modlabel()
{
for(int i = 0; i <= n; i++) d[i] = INF;
d[des] = 0;
dequeQ;
Q.push_back(des);
while(!Q.empty())
{
int u = Q.front(), tmp;
Q.pop_front();
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[edge[i].re].cap && (tmp = d[u] - edge[i].cost) < d[edge[i].v])
(d[edge[i].v] = tmp) <= d[Q.empty() src : Q.front()] Q.push_front(edge[i].v) : Q.push_back(edge[i].v);
}
for(int u = 1; u <= n; u++)
for(int i = head[u]; i != -1; i = edge[i].next)
edge[i].cost += d[edge[i].v] - d[u];
cost += d[src];
return d[src] < INF;
}
void costflow()
{
while(modlabel())
{
do
{
memset(vis, 0, sizeof(vis));
}while(aug(src, INF));
}
}
int nt, k;
int main()
{
int w;
while(scanf("%d%d", &nt, &k) != EOF)
{
init();
for(int i = 1; i <= nt; i++)
for(int j = 1; j <= nt; j++)
{
scanf("%d", &w);
int id = (i - 1) * nt + j;
add(id, id + nt * nt, 1, -w);
add(id, id + nt * nt, k, 0);
if(i < nt) add(id + nt * nt, id + nt, k, 0);
if(j < nt) add(id + nt * nt, id + 1, k, 0);
}
src = nt * nt * 2 + 1;
des = nt * nt * 2 + 2;
n = des;
add(src, 1, k, 0);
add(nt * nt * 2, des, k, 0);
costflow();
printf("%d\n", -ans);
}
return 0;
}

作者：sdj222555

POJ 3422 最小费用最大流 zkw或者普通版本 (三)