# UVA, 563 Crimewave

```#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
#define N 5005
#define INF 1000000
int q[4][2]= {1,0,0,1,-1,0,0,-1};
struct edge
{
int to,cap,rev;
edge(int a,int b,int c)
{
to=a;
cap=b;
rev=c;
}
};
vector<edge>v[N];
int dfs(int a,int t,int f);
int max_flow(int s,int t);
int used[N];
int vis[60][60];
int m,n,num;
int main()
{
int t;
cin>>t;

while(t--)
{
int a,b,c,d;
cin>>m>>n>>num;
// memset(vis,0,sizeof(vis));
for(int i=0; i<N; i++)
v[i].clear();
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
for(int k=0; k<4; k++)//和临点相连
{
int k1=i+q[k][0];
int k2=j+q[k][1];
if(k1>0&&k1<=m&&k2>0&&k2<=n)
{
}
}
}
}

for(int i=0; i<num; i++)//接下来的四个for循环是矩阵边缘的点和超级终点相连接。
{
cin>>c>>d;
}
for(int i=1; i<=n; i++)
{
}
if(m>1)
{
for(int i=1; i<=n; i++)
{
}
}
for(int i=2; i<m; i++)

if(n>1)
{
for(int i=2; i<m; i++)
}
int ans=max_flow(0,m*n*2+1);
//   cout<<ans;
if(ans==num)
cout<<"possible\n";
else
cout<<"not possible\n";
}
return 0;
}

{
v[from].push_back(edge(to,cap,v[to].size()));
v[to].push_back(edge(from,0,v[from].size()-1));
}
int dfs(int a,int t,int f)
{
if(a==t)
return f;
used[a]=1;
for(int i=0; i<v[a].size(); i++)
{
edge &e=v[a][i];
if(!used[e.to]&&e.cap>0)
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
v[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int flow=0;
while(1)
{
memset(used,0,sizeof(used));
int f=dfs(s,t,INF);
if(f==0)
return flow;
flow+=f;
}
}
```

## UVA 563 Crimewave (最大流，拆点)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=504  Crimewave  Nieuw Knollendam is a very modern town. This becomes clear already when looking at the layout of its map, which is just a rectangula

## uva 563 Crimewave（最大流）

Nieuw Knollendam is a very modern town. This becomes clear already when looking at the layout of its map, which is just a rectangular grid of streets and avenues. Being an important trade centre, Nieuw Knollendam also has a lot of banks. Almost on ev

## uva 563 Crimewave 最短路径

#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <cstdlib> #include <cmath> #include <set> #include <map> #include <vector> #include <cstri

## Crimewave (Uva 563 最大流拆点）

Crimewave  Nieuw Knollendam is a very modern town. This becomes clear already whenlooking at the layout of its map, which is just a rectangular grid of streetsand avenues. Being an important trade centre, Nieuw Knollendam also has a lotof banks. Alm

## Soj题目分类

-----------------------------最优化问题------------------------------------- ----------------------常规动态规划  SOJ1162 I-Keyboard  SOJ1685 Chopsticks SOJ1679 Gangsters SOJ2096 Maximum Submatrix  SOJ2111 littleken bg SOJ2142 Cow Exhibition  SOJ2505 The County