Matrix Again

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

28
46
80
分析：这道题和hdu 2628（Matrix）一模一样，只不过数据变大了，我一开始认为要卡时间或卡内存，可不知怎么优化，于是抱着试试的心态把数组开大结果过了。
那大家可以看一下我的hdu 2628 有讲解。
代码示例:
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<queue>#define Min(a,b) a<b?a:b#define inf 0xffffff#define maxn 4000000+10#define maxm 1000000+10using namespace std;typedef struct{    int from,to,next;    int val,cost;}node;node E[maxn];int head[maxm],dis[maxm],pre[maxm],pos[maxm],visit[maxm],cnt;void init(){    memset(head,-1,sizeof(head));    cnt=0;}void add(int from,int to,int val,int cost){    E[cnt].from=from,E[cnt].to=to,E[cnt].val=val,E[cnt].cost=cost;    E[cnt].next=head[from],head[from]=cnt++;    E[cnt].from=to,E[cnt].to=from,E[cnt].val=0,E[cnt].cost=-cost;    E[cnt].next=head[to],head[to]=cnt++;}bool spfa(int s,int t,int n){    int val,cost,to;    for(int i=0;i<=n;i++)    {        dis[i]=inf,visit[i]=0,pre[i]=-1;    }    dis[s]=0,visit[s]=1,pre[s]=s;    queue<int>Q;    Q.push(s);    while(!Q.empty())    {        int k=Q.front();        Q.pop();        visit[k]=0;        for(int i=head[k];i!=-1;i=E[i].next)        {            to=E[i].to,val=E[i].val,cost=E[i].cost;            if(val>0&&dis[k]+cost<dis[to])            {                dis[to]=dis[k]+cost;                pre[to]=k;                pos[to]=i;                if(visit[to])                continue;                visit[to]=1;                Q.push(to);            }        }    }    if(pre[t]!=-1&&dis[t]<inf)    return true;    return false;}int MinCostFlow(int s,int t,int n){    int netflow=0,costflow=0,min;    while(spfa(s,t,n))    {        min=inf;        for(int i=t;i!=s;i=pre[i])        {            min=Min(min,E[pos[i]].val);        }        netflow+=min;        costflow+=min*dis[t];        for(int i=t;i!=s;i=pre[i])        {            E[pos[i]].val-=min;            E[pos[i]^1].val+=min;        }    }    return -costflow;}int main(){    int n,s,t,x,sum;    while(~scanf("%d",&n))    {        init();        sum=0;        for(int i=0;i<n;i++)        for(int j=0;j<n;j++)        {            scanf("%d",&x);            if((i==0&&j==0)||(i==n-1&&j==n-1))            {                add(i*n+j,i*n+j+n*n,2,-x);                sum+=x;            }            else            {                add(i*n+j,i*n+j+n*n,1,-x);            }            if(i+1<n)            {                add(i*n+j+n*n,(i+1)*n+j,1,0);            }            if(j+1<n)            {                add(i*n+j+n*n,i*n+j+1,1,0);            }        }        s=2*n*n+1,t=2*n*n+2;        add(s,0,2,0);        add(2*n*n-1,t,2,0);        printf("%d\n",MinCostFlow(s,t,t+10)-sum);    }    return 0;}