F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 1001 >> dinic 1700MS
xiang556 @ 2018-07-10 06:37:21
[ Quote ] [ Edit ] [ Delete ] 1#
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <limits.h>
#define left (now<<1)
#define right ((now<<1)+1)
#define mid ((l+r)>>1)
#define fst first
#define snd second
#define sfn scanf("%d",&n)
#define sfnm scanf("%d%d",&n,&m)
#define sft scanf("%d",&t)
#define pfans printf("%d\n",ans)
using namespace std;
typedef long long lint;

const int MAXN = 1e6 + 10;

struct star{
int next,to,w;
};

int n,m,dis[MAXN],st,ed,last[MAXN],head[MAXN],len;
star g[6 * MAXN];
int line[MAXN];

int cul(int i,int j){
return (i - 1) * m + j;
}

void add(int u,int v,int w){
g[++len].to = v;
g[len].w = w;
g[len].next = head[u];
head[u] = len;
}

void next(int &x){
++x;
if(x > 1000001){
x = 0;
}
}

void bfs(){
int qst,qed,num = 1;
line[0] = st;
qst = 0; qed = 0;
memset(dis,-1,sizeof(dis));
dis[st] = 0;
while(num > 0){
int now = line[qst]; --num; next(qst);
for(int i = head[now]; i != -1; i = g[i].next){
if(dis[g[i].to] == -1 && g[i].w > 0){
dis[g[i].to] = dis[now] + 1;
next(qed); line[qed] = g[i].to;
++num;
}
}
}
}

int dinic(int now,int mlow){
int re = 0;
if(now == ed || mlow == 0){
return mlow;
}

for(int i = last[now]; i != -1; i = g[i].next){
last[now] = i;
if(g[i].w > 0 && dis[now] + 1 == dis[g[i].to]){
int flow = dinic(g[i].to,min(mlow,g[i].w));
if(flow > 0){
re += flow;
g[i].w -= flow;
g[i ^ 1].w += flow;
mlow -= flow;
if(mlow == 0){
last[now] == i;
break;
}
}
}
if(g[i].next == -1){
last[now] = -1;
}
}
return re;
}

void ceshi(){
for(int i = 1; i <= n * m; ++i){
printf("%I64d ",dis[i]);
if(i % m == 0){
printf("\n");
}
}
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n == m && n == 1){
int num; scanf("%d",&num);
printf("%d\n",num);
continue;
}
memset(head,-1,sizeof(head)); len = -1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j < m; ++j){
int num; scanf("%d",&num);
add(cul(i,j),cul(i,j + 1),num);
add(cul(i,j + 1),cul(i,j),num);
}
}

for(int i = 1; i < n; ++i){
for(int j = 1; j <= m; ++j){
int num; scanf("%d",&num);
add(cul(i,j),cul(i + 1,j),num);
add(cul(i + 1,j),cul(i,j),num);
}
}

for(int i = 1; i < n; ++i){
for(int j = 1; j < m; ++j){
int num; scanf("%d",&num);
add(cul(i,j),cul(i + 1,j + 1),num);
add(cul(i + 1,j + 1),cul(i,j),num);
}
}
st = 1; ed = n * m;
bfs(); int ans = 0;
while(dis[n * m] != -1){
memcpy(last,head,sizeof(head));
ans += dinic(st,INT_MAX);
bfs();
}
printf("%d\n",ans);
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back