COGS 栅格网络流

750. 栅格网络流

http://www.cogs.pro/cogs/problem/problem.php?pid=750

★★☆ 输入文件：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

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

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

平面图转对偶图求最小割

#include<cstdio>
#include<queue>
#include<cstring>
#define N 10010
#define M 50010
using namespace std;
int T,n,m,ans,tot;
int src,dec,next[M],to[M],front[N],cap[M];
long long DIS[N];
struct edge
{
    int number;
    long long dis;
    bool operator <(edge b) const
    {
        return dis>b.dis;
    }
}e[M];
priority_queue<edge>q;
void add(int u,int v,int w)
{
    to[++tot]=v;next[tot]=front[u];front[u]=tot;cap[tot]=w;
    to[++tot]=u;next[tot]=front[v];front[v]=tot;cap[tot]=w;
}
bool dijkstra()
{
    for(int i=1;i<=dec;i++) DIS[i]=2e9;
    q.push((edge){0,0});
    while(!q.empty())
    {
        edge now=q.top();q.pop();
        if(DIS[now.number]!=now.dis) continue;
        for(int i=front[now.number];i;i=next[i])
        {
            if(DIS[to[i]]>DIS[now.number]+1ll*cap[i])
            {
                DIS[to[i]]=DIS[now.number]+1ll*cap[i];
                q.push((edge){to[i],DIS[to[i]]});
            }
        }
    }
    printf("%d
",DIS[dec]);
}
void pre()
{
    tot=0;
    memset(front,0,sizeof(front));
}
int main()
{
    freopen("flowa.in","r",stdin);
    freopen("flowa.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        pre();
        scanf("%d%d",&n,&m);
        int x;
        for(int i=1;i<=n;i++)
         for(int j=1;j<m;j++)
          {
              scanf("%d",&x);
              add((i-1)*(m+1)+j,(i*(m+1)+j),x);
          }
        for(int i=1;i<n;i++)
         for(int j=1;j<=m;j++)
         {
             scanf("%d",&x);
             add(i*(m+1)+j-1,i*(m+1)+j,x);
         }
        dec=(n+1)*(m+1)-1;
        for(int i=m+1;i+m+1<=dec;i+=m+1)  add(src,i,0);
        for(int i=n*(m+1)+1;i<dec;i++) add(src,i,0);
        for(int i=1;i<m;i++) add(i,dec,0);
        for(int i=2*m+1;i+m<=dec;i+=m+1) add(i,dec,0);
        dijkstra();
    }
    return 0;
}

优先队列重载运算符记住里面是< 重载为 >