UVA, 563 Crimewave

题意:团伙抢完所有银行后,撤退到S*A矩阵外就算逃出,要求一个点不能走两次,问是否可以完全逃脱

这道题是最大流问题,主要是要去构建图,然后用最大流算法得出是否银行数量和逃出的数量相等。怎么构建图呢?主要是用拆点,把一个点拆成两个点,点(i,j)可以表示为:前点(i-1)*A+j,后点(i-1)*A+j+M(M为一个较大的数,保证M大于等于S*A就行),然后连接前点和后点,方向是前到后,

相邻的点,图是无向的,用该点的后点连接相邻点的前点。最后用一个超级源点连接所有的银行点的前点,用一个超级终点连接所有的边缘点的后点,所有边的权值为1,图就构建好了。然后用你们熟悉的最大流算法。

Ford-Fulkerson最大流算法代码参考:http://blog.csdn.net/itaskyou/article/details/51331344

#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];
void add_edge(int from,int to,int cap);
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++)
            {
                add_edge((i-1)*n+j,(i-1)*n+j+m*n,1);//每个点的前点和后点相连接
                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)
                    {
                        add_edge((i-1)*n+j+m*n,(k1-1)*n+k2,1);
                    }
                }
            }
        }

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

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

void add_edge(int from,int to,int cap)
{
    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;
    }
}
时间: 05-06

UVA, 563 Crimewave的相关文章

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 网络流

题目链接 有一个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(最大流)

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

Uva 563 网络流

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

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

网络流专栏

最大流 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance(构图) POJ 1459 Power Network(构图) POJ 2112 Optimal Milking (二分) POJ 2455 Secret Milking Machine (二分) POJ 3189 Steady Cow Assignment (枚举) POJ 1637 Sightseeing tour (

Soj题目分类

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

网络流柱

最大流量 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance(构图) POJ 1459 Power Network(构图) POJ 2112 Optimal Milking (二分) POJ 2455 Secret Milking Machine (二分) POJ 3189 Steady Cow Assignment (枚举) POJ 1637 Sightseeing tour