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 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 of  and 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) and y (the number of the avenue). Evidently  and .

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


Miguel A. Revilla

1998-03-10

题意:

有若干罪犯抢银行,要求逃出地图时他们的路线不相交,求是否能达到上述要求。

分析:

路线不相交即每个点每条边只能用一次,即容量为1,点上的流量限制拆点即可。源点连向罪犯所在位置的入点,最外一圈的出点连向汇点,满流即可能。

/*
 *
 *	Author	:	fcbruce
 *
 *	Date	:	2014-09-04 21:26:22
 *
 */
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
	#define lld "%I64d"
#else
	#define lld "%lld"
#endif

#define maxm 2333333
#define maxn 8964

using namespace std;

int fir[maxn];
int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
int e_max;
int iter[maxn],q[maxn],lv[maxn];

void add_edge(int _u,int _v,int _w)
{
    int e;
    e=e_max++;
    u[e]=_u;v[e]=_v;cap[e]=_w;
    nex[e]=fir[u[e]];fir[u[e]]=e;
    e=e_max++;
    u[e]=_v;v[e]=_u;cap[e]=0;
    nex[e]=fir[u[e]];fir[u[e]]=e;
}

void dinic_bfs(int s)
{
    int f,r;
    memset(lv,-1,sizeof lv);
    q[f=r=0]=s;
    lv[s]=0;
    while(f<=r)
    {
        int x=q[f++];
        for (int e=fir[x];~e;e=nex[e])
        {
            if (cap[e]>flow[e] && lv[v[e]]<0)
            {
                lv[v[e]]=lv[u[e]]+1;
                q[++r]=v[e];
            }
        }
    }
}

int dinic_dfs(int _u,int t,int _f)
{
    if (_u==t)  return _f;
    for (int &e=iter[_u];~e;e=nex[e])
    {
        if (cap[e]>flow[e] && lv[_u]<lv[v[e]])
        {
            int _d=dinic_dfs(v[e],t,min(_f,cap[e]-flow[e]));
            if (_d>0)
            {
                flow[e]+=_d;
                flow[e^1]-=_d;
                return _d;
            }
        }
    }

    return 0;
}

int max_flow(int s,int t)
{

    memset(flow,0,sizeof flow);
    int total_flow=0;

    for (;;)
    {
        dinic_bfs(s);
        if (lv[t]<0)    break;
        memcpy(iter,fir,sizeof iter);
        int _f;

        while ((_f=dinic_dfs(s,t,INF))>0)
            total_flow+=_f;
    }

    return total_flow;
}

int main()
{
	#ifdef FCBRUCE
		freopen("/home/fcbruce/code/t","r",stdin);
	#endif // FCBRUCE

	int T_T;

	scanf( "%d",&T_T);

	while (T_T--)
	{
		int n,m,s=0,t=8963;
		scanf( "%d%d",&n,&m);

		e_max=0;
		memset(fir,-1,sizeof fir);

		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				add_edge(i*m+j+n*m,i*m+j,1);

				if (i==n || j==m) continue;

				add_edge(i*m+j,(i+1)*m+j+n*m,1);
				add_edge(i*m+j,i*m+j+1+n*m,1);

				add_edge((i+1)*m+j,i*m+j+n*m,1);
				add_edge(i*m+j+1,i*m+j+n*m,1);
			}

		for (int i=1;i<=m;i++)
		{
			add_edge(1*m+i,t,1);
			add_edge(n*m+i,t,1);
		}

		for (int i=2;i<n;i++)
		{
			add_edge(i*m+1,t,1);
			add_edge(i*m+m,t,1);
		}

		int p;
		scanf( "%d",&p);
		for (int i=0,x,y;i<p;i++)
		{
			scanf( "%d%d",&x,&y);
			add_edge(s,x*m+y+n*m,1);
		}

		if (max_flow(s,t)==p)
			puts( "possible");
		else
			puts( "not possible");
	}

	return 0;
}
时间: 09-02

UVA 563 Crimewave (最大流,拆点)的相关文章

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

题意:团伙抢完所有银行后,撤退到S*A矩阵外就算逃出,要求一个点不能走两次,问是否可以完全逃脱 这道题是最大流问题,主要是要去构建图,然后用最大流算法得出是否银行数量和逃出的数量相等.怎么构建图呢?主要是用拆点,把一个点拆成两个点,点(i,j)可以表示为:前点(i-1)*A+j,后点(i-1)*A+j+M(M为一个较大的数,保证M大于等于S*A就行),然后连接前点和后点,方向是前到后, 相邻的点,图是无向的,用该点的后点连接相邻点的前点.最后用一个超级源点连接所有的银行点的前点,用一个超级终点连

uva 563 - Crimewave 网络流

题目链接 有一个n*m的图, 里面有q个人, 每个点只能走一次, 问这q个人是否都能够走出这个图. 对于每个人, 建边(s, u, 1), 对于每个边界的格子, 建边(u', t, 1), 对于其他格子, 建边(u, u', 1), 以及(u', v, 1), v是它四周的格子. 对于求出的最大流, 如果等于人数, 则可以走出. 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #de

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

Uva 563 网络流

题目链接:点击打开链接 题意:给定s*a的方格点,有b个坐标是有且仅有一个人的. 每个点只能被经过一次 能不能让所有人都移动到矩阵边缘. 拆点一下,建图还是挺明显的.. 太卡了提交半天没结果,贴一下代码改天再搞好了.. //好吧1A了.. #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> using namesp

hdu 4289 Control(网络流 最大流+拆点)(模板)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4289 Control Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1545    Accepted Submission(s): 677 Problem Description You, the head of Department o

POJ3422 Kaka&#39;s Matrix Travels(最大费用最大流 + 拆点)

题目链接:http://poj.org/problem?id=3422 题意:有一个n*n的矩阵,格子中的元素是费用,KaKa从左上角开始出发要到达右下角,但是他只能向下走或者向右走,且走过的格子赋值为0,可以走K次,问K次后KaKa能获得的最大费用是多少? 思路:首先解释一下为什么要拆点?    因为要获得最大费用,所以假设当前步选择先下走,最终得到的结果可能不是最大值,但根据题意却把走过的格子赋为0了,这就影响了最终结果.所以进行拆点,把每个点拆成两个点,入度点和出度点,本点的入度点连接着本

HDU 2686 Matrix(最大费用最大流+拆点)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2686 和POJ3422一样 删掉K把汇点与源点的容量改为2(因为有两个方向的选择)即可 #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int ma

POJ 3422 Kaka&#39;s Matrix Travels(最大费用最大流 + 拆点)

题目链接:http://poj.org/problem?id=3422 Description On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking