比赛 |
20140423 |
评测结果 |
AWWWWWWEEE |
题目名称 |
栅格网络流 |
最终得分 |
10 |
用户昵称 |
超级傲娇的AC酱 |
运行时间 |
1.017 s |
代码语言 |
C++ |
内存使用 |
0.32 MiB |
提交时间 |
2014-04-23 11:15:09 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int Mins,m,n;
bool v[10010];
//int C[500][500],F[500][500];
vector<vector<int> >C,F;
const int oo=(1<<30);
void init();
int DFS(int,int);
int main()
{
int i,j,k,p,T,Ans=0;
freopen("flowa.in","r",stdin);
freopen("flowa.out","w",stdout);
cin>>T;
for(i=0;i<T;i++)
{
cin>>n>>m;
C.clear();F.clear();
C.resize(m*n);F.resize(m*n);
for(j=0;j<m*n;j++)
{
C[j].resize(m*n);
F[j].resize(m*n);
}
for(j=0;j<n;j++)
for(k=0;k<m-1;k++)
{
cin>>p;
C[j*m+k][j*m+k+1]=C[j*m+k+1][j*m+k]=p;
}
for(j=0;j<n-1;j++)
for(k=0;k<m;k++)
{
cin>>p;
C[j*m+k][(j+1)*m+k]=C[(j+1)*m+k][j*m+k]=p;
}
for(;;)
{
init();
if(DFS(oo,0)==0)
break;
}
for(j=0;j<m*n;j++)
Ans+=F[j][m*n-1];
cout<<Ans<<endl;
}
return 0;
}
void init()
{
for(int i=0;i<m*n;i++)
v[i]=false;
Mins=0;
}
int DFS(int Max,int pos)
{
v[pos]=true;
if(pos==m*n-1)
{
Mins=Max;
return Mins;
}
else
{
for(int i=0;i<m*n;i++)
{
if(C[pos][i]-F[pos][i]>0&&v[i]==false)
{
if(v[m*n-1]==false)
Mins=DFS(min(Max,C[pos][i]-F[pos][i]),i);
if(v[m*n-1]==true)
{
F[pos][i]+=Mins;
F[i][pos]=-F[pos][i];
return Mins;
}
}
}
return 0;
}
}