记录编号	37751	评测结果	AAAAAAAAAA
题目名称	栅格网络流	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.137 s
提交时间	2012-04-07 11:06:17	内存使用	0.64 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef long long Int;
const int MAXN=11000;
const Int INF=Int(1e12);
vector<int> Map[MAXN];
vector<Int> Val[MAXN];
queue<int> Q;
Int dist[MAXN];
int flag[MAXN];
int T,N,M,Source,Sink;

inline void SPFA()
{
    for(int i=0;i<=Sink;i++) dist[i]=INF;
    dist[Source]=0;
    Q.push(Source);
    flag[Source]=1;
    int u,v;
    Int nxt;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        flag[u]=0;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i];
            nxt=dist[u]+Val[u][i];
            if(nxt<dist[v])
            {
                dist[v]=nxt;
                if(!flag[v])
                {
                    Q.push(v);
                    flag[v]=1;
                }
            }
        }
    }
    printf("%lld\n",dist[Sink]);
}

void AddEdge(int s,int e,Int f)
{
	Map[s].push_back(e);
	Val[s].push_back(f);
	Map[e].push_back(s);
	Val[e].push_back(f);
}

void init()
{
	scanf("%d\n",&T);
	Int x;
	while(T--)
	{
		scanf("%d %d\n",&N,&M);
		for(int i=0;i<=10010;i++) { Map[i].clear(); Val[i].clear(); }
		Source=0,Sink=(N-1)*(M-1)+1;
		/*以下橫向*/
		for(int i=1;i<=M-1;i++)
		{
			scanf("%lld",&x); 
			AddEdge(Source,i,x);
		}
		for(int i=2;i<=N-1;i++)
		{
			for(int j=1;j<=M-1;j++)
			{
				scanf("%lld",&x);
				AddEdge((i-2)*(M-1)+j,(i-1)*(M-1)+j,x);
			}
		}
		for(int i=1;i<=M-1;i++)
		{
			scanf("%lld",&x);
			AddEdge(Sink,(N-2)*(M-1)+i,x);
		}
		/*以下縱向*/
		for(int i=1;i<=N-1;i++)
		{
			scanf("%lld",&x);
			AddEdge(Sink,(i-1)*(M-1)+1,x);
			for(int j=2;j<=M-1;j++)
			{
				scanf("%lld",&x);
				AddEdge((i-1)*(M-1)+j-1,(i-1)*(M-1)+j,x);
			}
			scanf("%lld",&x);
			AddEdge(Source,i*(M-1),x);
		}
		SPFA();
	}
}

int main()
{
	freopen("flowa.in","r",stdin);
	freopen("flowa.out","w",stdout);
	init();
	return 0;
}