比赛 |
20140423 |
评测结果 |
AAAWWWAAWW |
题目名称 |
栅格网络流 |
最终得分 |
50 |
用户昵称 |
隨風巽 |
运行时间 |
0.041 s |
代码语言 |
C++ |
内存使用 |
0.46 MiB |
提交时间 |
2014-04-23 11:00:04 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 200000000
using namespace std;
struct Edge{int from,to,cap,flow;};
const int MAXN=10000+10;
struct Dinic
{
int n,m,s,t;
vector<Edge>edges;
vector<int>g[MAXN];
queue<int>q;
bool visited[MAXN];
int d[MAXN],cur[MAXN];
void INITIALIZE(int n)
{
this->n=n;
for(int i=0;i<=n;i++)g[i].clear();
edges.clear();
}
void ADD(int from,int to,int cap)
{
edges.push_back((Edge){from,to,cap,0});
edges.push_back((Edge){to,from,0,0});
m=edges.size();
g[from].push_back(m-2);
g[to].push_back(m-1);
}
bool BFS(void)
{
int v,i;
memset(visited,0,sizeof(visited));
q.push(s);
d[s]=0;visited[s]=true;
while(!q.empty())
{
v=q.front();q.pop();
for(i=0;i<g[v].size();i++)
{
Edge &e=edges[g[v][i]];
if(not visited[e.to]&&e.cap>e.flow)
{
d[e.to]=d[v]+1;
q.push(e.to);
visited[e.to]=true;
}
}
}
return visited[t];
}
int DFS(int v,int a)
{
if(v==t||a==0)return a;
int flow=0,f;
for(int& i=cur[v];i<g[v].size();i++)
{
Edge& e=edges[g[v][i]];
if(d[v]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
edges[g[v][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)break;
}
}
return flow;
}
int MAXFLOW(int s,int t)
{
int flow=0;
this->s=s;this->t=t;
while(BFS())
{
memset(cur,0,sizeof(cur));
flow+=DFS(s,INF);
}
return flow;
}
};
Dinic NF;
int T,N,M,F;
int ID(int i,int j){return (i-1)*M+j;}
int main()
{
freopen("flowa.in","r",stdin);
freopen("flowa.out","w",stdout);
int i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&M);
NF.INITIALIZE(ID(N,M));
for(i=1;i<=N;i++)
for(j=1;j<=M-1;j++)
{
scanf("%d",&F);
NF.ADD(ID(i,j),ID(i,j+1),F);
}
for(i=1;i<=N-1;i++)
for(j=1;j<=M;j++)
{
scanf("%d",&F);
NF.ADD(ID(i,j),ID(i+1,j),F);
}
cout<<NF.MAXFLOW(ID(1,1),ID(N,M))<<endl;
}
return 0;
}