小白书训练计划|UVa563_Crimewave(网络流/最大流)(小白书图论专题)
解题报告
思路：
要求抢劫银行的伙伴（想了N多名词来形容，强盗，贼匪，小偷，sad，都觉得不合适）不在同一个路口相碰面，可以把点拆成两个点，一个入点，一个出点。
再设计源点s连向银行位置，再矩阵外围套上一圈，连向汇点t
矩阵内的点，出点和周围的点的出点相连。
#include
#include
#include
#include
#define M 500000
#define N 10000
#define inf 0x3f3f3f3f
using namespace std;
int n,m,h,w,head[N],pre[N],l[N],mmap[N][N],cnt,s,t;
struct node {
intv,w,next;
} edge[M];
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};
void add(int u,int v,int w) {
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].v=u;
edge[cnt].w=0;
edge[cnt].next=head[v];
head[v]=cnt++;
}
int bfs() {
memset(l,-1,sizeof(l));
l[s]=0;
int i,u,v;
queueQ;
Q.push(s);
while(!Q.empty()) {
u=Q.front();
Q.pop();
for(i=head[u];
i!=-1;
i=edge[i].next) {
v=edge[i].v;
if(l[v]==-1&&edge[i].w) {
l[v]=l[u]+1;
Q.push(v);
}
}
}
return l[t]>0;
}
int dfs(int u,int f) {
int a,flow=0;
if(u==t)return f;
for(int i=head[u];
i!=-1;
i=edge[i].next) {
int v=edge[i].v;
if(l[v]==l[u]+1&&edge[i].w&&(a=dfs(v,min(f,edge[i].w)))) {
edge[i].w-=a;
edge[i^1].w+=a;
flow+=a;
f-=a;
if(!f)break;
}
}
if(!flow)l[u]=-1;
return flow;
}
int main() {
int i,j,T,k,x,y;
scanf("%d",&T);
while(T--) {
cnt=k=0;
memset(head,-1,sizeof(head));
scanf("%d%d%d",&h,&w,&m);
h+=2;
w+=2;
for(i=0;
i=1&&x=1&&y
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 every crossing a bank is found (although there are never two banks at the same crossing). Unfortunately this has attracted a lot of criminals. Bank hold-ups are quite common, and often on one day several banks are robbed. This has grown into a problem, not only to the banks, but to the criminals as well. After robbing a bank the robber tries to leave the town as soon as possible, most of the times chased at high speed by the police. Sometimes two running criminals pass the same crossing, causing several risks: collisions, crowds of police at one place and a larger risk to be caught.
To prevent these unpleasant situations the robbers agreed to consult together. Every Saturday night they meet and make a schedule for the week to come: who is going to rob which bank on which day? For every day they try to plan the get-away routes, such that no two routes use the same crossing. Sometimes they do not succeed in planning the routes according to this condition, although they believe that such a planning should exist.
Given a grid ofand the crossings where the banks to be robbed are located, find out whether or not it is possible to plan a get-away route from every robbed bank to the city-bounds, without using a crossing more than once.
Input
The first line of the input contains the number of problems
p
to be solved.
- The first line of every problem contains the number s of streets ( ), followed by the number a of avenues (), followed by the number b () of banks to be robbed.
- Then b lines follow, each containing the location of a bank in the form of two numbers x (the number of the street) andy (the number of the avenue). Evidentlyand .
Output
The output file consists of
p
lines. Each line contains the text
possible
or
not possible
. If it is possible to plan non-crossing get-away routes, this line should contain the word:
possible
. If this is not possible, the line should contain the words
not possible
.
Sample Input
2
6 6 10
4 1
3 2
4 2
5 2
3 4
4 4
5 4
3 6
4 6
5 6
5 5 5
3 2
2 3
3 3
4 3
3 4
Sample Output
possible
not possible
【小白书训练计划|UVa563_Crimewave(网络流/最大流)(小白书图论专题)】
Miguel A. Revilla
1998-03-10
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 图书集合完毕
- “成长”读书社群招募
- 书评——《小行星》
- 【0212读书感悟】
- 历史教学书籍
- 绘本讲师训练营【24期】14/21阅读原创《小黑鱼》
- 绘本讲师训练营【18期】14/21《我的情绪小怪兽》故事会新体验
- 合理情绪疗法之试用｜李克富思维训练营56/90
- 我正在参加安特思库共读一本书干法。
- 绘本讲师训练营7期9/21阅读原创《蜗牛屋|绘本讲师训练营7期9/21阅读原创《蜗牛屋 》