首页 > 代码库 > hdu 1569 最大流
hdu 1569 最大流
擦，搞了几个模板，都有错，就这个还好吧
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 3000;
struct arc {
int to,flow,next;
arc(int x = 0,int y = 0,int z = 0) {
to = x;
flow = y;
next = z;
}
};
arc e[maxn*10];
int head[maxn],d[maxn],tot;
int S,T,q[maxn],hd,tail,n,m;
void add(int u,int v,int flow) {
e[tot] = arc(v,flow,head[u]);
head[u] = tot++;
e[tot] = arc(u,0,head[v]);
head[v] = tot++;
}
bool bfs() {
for(int i = 1; i <= T; i++) d[i] = 0;
d[S] = 1;
hd = tail = 0;
q[tail++] = S;
while(hd < tail) {
int u = q[hd++];
for(int i = head[u]; ~i; i = e[i].next) {
if(e[i].flow && !d[e[i].to]) {
d[e[i].to] = d[u]+1;
q[tail++] = e[i].to;
}
}
}
return d[T];
}
int dfs(int u,int low) {
int tmp = 0,f;
if(u == T || !low) return low;
for(int i = head[u]; ~i; i = e[i].next) {
if(d[e[i].to] == d[u]+1 && (f = dfs(e[i].to,min(low,e[i].flow)))) {
tmp += f;
e[i].flow -= f;
e[i^1].flow += f;
low -= f;
if(!low) break;
}
}
return tmp;
}
void init(){
memset(head,-1,sizeof(head));
tot = 0;
}
int main(){
while(scanf("%d%d", &m,&n) != EOF)
{
init();
int x;
int sum = 0;
S = 0;
T = m * n + 1;
for(int i = 1; i <= m; ++ i)
for(int j = 1; j <= n; ++ j)
{
scanf("%d", &x);
sum += x;
if((i + j) & 1)
{
add(S, (i - 1) * n + j, x);
//上
if(i > 1) add((i - 1) * n + j, (i - 2) * n + j, INF);
//下
if(i < m) add((i - 1) * n + j, i * n + j, INF);
//左
if(j > 1) add((i - 1) * n + j, (i -1) * n + j - 1, INF);
//右
if(j < n) add((i - 1) * n + j, (i - 1) * n + j + 1, INF);
}
else
add((i - 1) * n + j, T, x);
}
int ans = 0;
while(bfs())ans+=dfs(S,INF);
printf("%d\n",sum - ans);
}
}
原来边就有权值的：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 3000;
struct arc {
int to,cap,flow,next;
arc(int x= 0 ,int y=0 ,int z=0 ,int u=0) {
to = x;
cap = y;
flow = z;
next = u;
}
};
arc e[maxn*10];
int head[maxn],d[maxn],tot;
int S,T,q[maxn],hd,tail,n,m;
void add(int u,int v,int cap,int flow) {
e[tot] = arc(v,cap,flow,head[u]);
head[u] = tot++;
e[tot] = arc(u,0,-flow,head[v]);
head[v] = tot++;
}
bool bfs() {
for(int i = 1; i <= T; i++) d[i] = 0;
d[S] = 1;
hd = tail = 0;
q[tail++] = S;
while(hd < tail) {
int u = q[hd++];
for(int i = head[u]; ~i; i = e[i].next) {
if(e[i].cap > e[i].flow && !d[e[i].to]) {
d[e[i].to] = d[u]+1;
q[tail++] = e[i].to;
}
}
}
return d[T];
}
int dfs(int u,int low) {
int tmp = 0,f;
if(u == T || !low) return low;
for(int i = head[u]; ~i; i = e[i].next) {
if(d[e[i].to] == d[u]+1 && (f = dfs(e[i].to,min(low,e[i].cap-e[i].flow)))) {
tmp += f;
e[i].flow += f;
e[i^1].flow -= f;
low -= f;
if(!low) break;
}
}
return tmp;
}
void init(){
memset(head,-1,sizeof(head));
tot = 0;
}
int main(){
while(scanf("%d%d", &m,&n) != EOF)
{
init();
int x;
int sum = 0;
S = 0;
T = m * n + 1;
for(int i = 1; i <= m; ++ i)
for(int j = 1; j <= n; ++ j)
{
scanf("%d", &x);
sum += x;
if((i + j) & 1)
{
add(S, (i - 1) * n + j, x,0);
//上
if(i > 1) add((i - 1) * n + j, (i - 2) * n + j, INF,0);
//下
if(i < m) add((i - 1) * n + j, i * n + j, INF,0);
//左
if(j > 1) add((i - 1) * n + j, (i -1) * n + j - 1, INF,0);
//右
if(j < n) add((i - 1) * n + j, (i - 1) * n + j + 1, INF,0);
}
else
add((i - 1) * n + j, T, x,0);
}
int ans = 0;
while(bfs())ans+=dfs(S,INF);
printf("%d\n",sum - ans);
}
}
hdu 1569 最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。