hdu 3870 Catch the Theves 夜

http://acm.hdu.edu.cn/showproblem.php?pid=3870

最大流 转换成 最小割      最小割 转换成 最短路

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>

//#define ull unsigned long long
#define ll long long

using namespace std;

const int INF=0x3f3f3f3f;
const ll LINF=1e18;

const int N=400000;
const int M=1000000;
int head[N],I;
struct node
{
    int j,next;
    int d;
}edge[M];
int dist[N];
bool in[N];
int a[500][500];
void add(int i,int j,int d)
{
    edge[I].j=j;
    edge[I].d=d;
    edge[I].next=head[i];
    head[i]=I++;
}
void init(int st,int nd,int n)
{
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
    scanf("%d",&a[i][j]);
    memset(head,-1,sizeof(head));
    I=0;
    for(int i=0;i<n-1;++i)
    for(int j=0;j<n-1;++j)
    {
        int l=i*n+j;
        if(i==0)
        add(l,nd,a[i][j]);
        else
        add(l,(i-1)*n+j,a[i][j]);
        if(j==0)
        add(st,l,a[i][j]);
        else
        add(l,i*n+j-1,a[i][j]);
        if(i==n-2)
        add(st,l,a[i+1][j]);
        else
        add(l,(i+1)*n+j,a[i+1][j]);
        if(j==n-2)
        add(l,nd,a[i][j+1]);
        else
        add(l,i*n+j+1,a[i][j+1]);
    }
}
int spfa(int x1,int x2)
{
    memset(in,false,sizeof(in));
    memset(dist,-1,sizeof(dist));
    queue<int>qt;
    qt.push(x1);
    dist[x1]=0;
    in[x1]=true;
    while(!qt.empty())
    {
        int x=qt.front();
        qt.pop();in[x]=false;
        for(int t=head[x];t!=-1;t=edge[t].next)
        {
            int j=edge[t].j;
            int d=edge[t].d;
            if(dist[j]==-1||dist[j]>dist[x]+d)
            {
                dist[j]=dist[x]+d;
                if(!in[j])
                {
                    in[j]=true;
                    qt.push(j);
                }
            }
        }
    }
    return dist[x2];
}
int main()
{
    //freopen("data.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int st=n*n;
        int nd=st+1;
        init(st,nd,n);
        printf("%d\n",spfa(st,nd));
    }
    return 0;
}