栅格网络流

★★☆   输入文件：flowa.in   输出文件：flowa.out   简单对比
时间限制：1 s   内存限制：128 MB

【问题描述】

Bob 觉得一般图的最大流问题太难了，他不知道如何解决，于是他想尝试一个简单点的：栅格网络中的最大流问题，这个虽说简单了一点，但对 Bob 来说依旧太难，现在他有个麻烦需要你帮忙：给你一个 N*M 的栅格（如下所示），栅格中的边表示可以流水的管道，边上的数字表示管道的容量，举例说明：在下面图（ 2.6.1 ）中， (0,0) 和 (1,0) 之间边的容量为 6 ，这意味着这条边（水管）的最大水流量不超过 6 个单位。

N=3 M=3
图 2.6.1 栅格网络流

那么栅格中从 S 到 T 的最大流是多少呢 ? 换句话说 , 某一时刻最多能有多少单位的水从 S 流向 T?

【输入格式】

输入文件的第一行是一个正整数 T ，表示接下来有多少组测试数据。

每一组测试数据的第一行有两个正整数 N,M(1<=N,M<=100)<n<100) 和="" m(1<m<100)="" 。接下来有两个整数矩阵="" h="" （="" n*(m-1)="" ）和="" v="" (n-1)*m="" ），="" h[i][j]="" 表示="" (i,j)="" 与="" (i,j+1)="" 之间边的容量，="" v[i][j]="" (i+1,j)="" 中所有的数均非负且小于="" 10^10="" 。<="" p="">

接着有两个矩阵H(N*(M-1)),V((N-1)*M)，H[i][j]表示(i,j)->(i,j+1)的流量；

V[i][j]表示(i,j)->(i+1,j)的流量。

【输出格式】

每一组测试数据输出只有一行，包含一个整数，即从 S(0,0) 到 T(N-1,M-1) 的栅格网络的最大流，不允许出现多余的空格。

【输入样例】

输入文件名： flowa .in

1
3 3
0 1
2 3
4 5
6 7 8
9 10 11

输出文件名： flowa .out

6

提示：下图 (2.6.2) 所示即为样例中栅格中的一个最大流。

N=3 M=3
图 2.6.2 一个解决方案

思路：对偶图转化+SPFA||最大流

这个图直接跑最大流会T的（师傅说的）。

先把图重构，然后跑一个最小截断路（最小割）。

构图，like this.

由于在某bzoj 1001重构对偶图T掉了，所以回来试试Dinic，结果明显Dinic更优。

所以说，这种题，老老实实写个最大流就好了。

代码实现：

重构对偶图

100

C++

0.050 s

6.17 MB

2017-03-12 17:05:23

#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000000000ll
using namespace std;
int test,n,m,s,t;
int a,b,c,l;
int h[12100],hs=1;
struct edge{int s,n;long long w;}e[300000];
int q[300000],head,tail;
long long la,lb;
long long w[12100];
char ch[30];
long long read(){
    long long ret=0;l=0;
    do{ch[0]=getchar();}while(ch[0]<'0'||ch[0]>'9');
    l++;
    do{ch[l++]=getchar();}while(ch[l-1]>='0'&&ch[l-1]<='9');
    l-=2;
    for(long long i=l,j=1;i>=0;i--,j*=10) ret+=(ch[i]-'0')*j;
    return ret;
}
void write(long long x){
    if(!x) return;
    write(x/10);
    putchar(x%10+'0');
}
int main(){
    freopen("flowa.in","r",stdin);
    freopen("flowa.out","w",stdout);
    scanf("%d",&test);
    while(test--){
        memset(h,0,sizeof(h)),hs=1;
        scanf("%d%d",&n,&m);
        s=m+1,t=n*m+n+1;
        for(int i=2;i<=m;i++){
            a=n*m+n+i;
            e[++hs]=(edge){i,h[s],0},h[s]=hs;
            e[++hs]=(edge){t,h[a],0},h[a]=hs;
        }
        for(int i=1;i<n;i++){
            a=(i+1)*(m+1),b=i*(m+1)+1;
            e[++hs]=(edge){a,h[s],0},h[s]=hs;
            e[++hs]=(edge){t,h[b],0},h[b]=hs;
        }
        for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++){
            la=read();
            b=i*m-m+i+j,c=b+m+1;
            e[++hs]=(edge){c,h[b],la},h[b]=hs;
            e[++hs]=(edge){b,h[c],la},h[c]=hs;
        }
        for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++){
            la=read();
            b=i*m+i+j+1,c=b-1;
            e[++hs]=(edge){c,h[b],la},h[b]=hs;
            e[++hs]=(edge){b,h[c],la},h[c]=hs;
        }
        for(int i=1;i<=(n+1)*(m+1);i++) w[i]=inf;
        head=tail=0;
        w[s]=0,q[head++]=s;
        while(head>tail){
            a=q[tail++];
            for(int i=h[a];i;i=e[i].n){
                la=w[a]+e[i].w,lb=w[e[i].s];
                if(la<lb) w[e[i].s]=la,q[head++]=e[i].s;
            }
        }
        write(w[t]);
        if(!w[t]) putchar('0');
        putchar('
');
    }
    return 0;
}

Dinic

100

C++

0.022 s

1.19 MB

2017-03-18 10:35:25

#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000000000ll
using namespace std;
int test,n,m,s,t;
int a,b,c,l;
long long la,lb,wt;
int d[10010],q[10010],head,tail;
int h[10010],hs=1;
struct edge{int s,n;long long w;}e[50000];
char ch[30];
long long read(){
    long long ret=0;l=0;
    do{ch[0]=getchar();}while(ch[0]<'0'||ch[0]>'9');
    l++;
    do{ch[l++]=getchar();}while(ch[l-1]>='0'&&ch[l-1]<='9');
    l-=2;
    for(long long i=l,j=1;i>=0;i--,j*=10) ret+=(ch[i]-'0')*j;
    return ret;
}
void write(long long x){
    if(!x) return;
    write(x/10);
    putchar(x%10+'0');
}
inline long long min(long long x,long long y){return x<y?x:y;}
void bfs(){
    memset(d,0,sizeof(d));
    head=tail=0;
    d[s]=1,q[head++]=s;
    while(head>tail){
        a=q[tail++];
        for(int i=h[a];i;i=e[i].n)
        if(!d[e[i].s]&&e[i].w){
            d[e[i].s]=d[a]+1;
            if(e[i].s==t) return;
            q[head++]=e[i].s;
        }
    }
}
long long ap(int k,long long nw){
    if(k==t) return nw;
    long long bw=nw;
    for(int i=h[k];i&&bw;i=e[i].n)
    if(e[i].w&&d[e[i].s]==d[k]+1){
        long long dw=ap(e[i].s,min(bw,e[i].w));
        if(dw) e[i].w-=dw,e[i^1].w+=dw,bw-=dw;
        else d[e[i].s]=0;
    }
    return nw-bw;
}
bool Dinic(){
    bfs();
    if(!d[t]) return 0;
    wt+=ap(s,inf);
    return 1;
}
int main(){
    freopen("flowa.in","r",stdin);
    freopen("flowa.out","w",stdout);
    test=read();
    while(test--){
        memset(h,0,sizeof(h)),hs=1,wt=0;
        n=read(),m=read();
        s=1,t=n*m;
        for(int i=0;i<n;i++)
        for(int j=1;j<m;j++){
            la=read();
            a=i*m+j,b=a+1;
            e[++hs]=(edge){b,h[a],la},h[a]=hs;
            e[++hs]=(edge){a,h[b],la},h[b]=hs;
        }
        for(int i=0;i<n-1;i++)
        for(int j=1;j<=m;j++){
            la=read();
            a=i*m+j,b=a+m;
            e[++hs]=(edge){b,h[a],la},h[a]=hs;
            e[++hs]=(edge){a,h[b],la},h[b]=hs;
        }
        while(Dinic());
        if(!wt) putchar('0');
        write(wt);
        putchar('
');
    }
    return 0;
}

开long long！！！

题目来源：COGS