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 #define ll long long
  5 #define mk(x, y) make_pair(x, y)
  6 #define lson l, m, rt<<1
  7 #define mem(a) memset(a, 0, sizeof(a))
  8 #define rson m+1, r, rt<<1|1
  9 #define mem1(a) memset(a, -1, sizeof(a))
 10 #define mem2(a) memset(a, 0x3f, sizeof(a))
 11 #define rep(i, a, n) for(int i = a; i<n; i++)
 12 #define ull unsigned long long
 13 typedef pair<int, int> pll;
 14 const double PI = acos(-1.0);
 15 const double eps = 1e-8;
 16 const int mod = 1e9+7;
 17 const int inf = 1061109567;
 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
 19 const int maxn = 2e6+5;
 20 int num, q[maxn*5], head[maxn*2], dis[maxn*2], s, t;
 21 struct node
 22 {
 23     int to, nextt, c;
 24     node(){}
 25     node(int to, int nextt, int c):to(to), nextt(nextt), c(c){}
 26 }e[maxn*2];
 27 int bfs() {
 28     mem(dis);
 29     int st = 0, ed = 0;
 30     dis[s] = 1;
 31     q[ed++] = s;
 32     while(st<ed) {
 33         int u = q[st++];
 34         for(int i = head[u]; ~i; i = e[i].nextt) {
 35             int v = e[i].to;
 36             if(!dis[v]&&e[i].c) {
 37                 dis[v] = dis[u]+1;
 38                 if(v == t)
 39                     return 1;
 40                 q[ed++] = v;
 41             }
 42         }
 43     }
 44     return 0;
 45 }
 46 int dfs(int u, int limit) {
 47     int cost = 0;
 48     if(u == t)
 49         return limit;
 50     for(int i = head[u]; ~i; i = e[i].nextt) {
 51         int v = e[i].to;
 52         if(e[i].c&&dis[v] == dis[u]+1) {
 53             int tmp = dfs(v, min(e[i].c, limit-cost));
 54             if(tmp>0) {
 55                 e[i].c -= tmp;
 56                 e[i^1].c += tmp;
 57                 cost += tmp;
 58                 if(cost == limit)
 59                     break;
 60             } else {
 61                 dis[v] = -1;
 62             }
 63         }
 64     }
 65     return cost;
 66 }
 67 int dinic() {
 68     int ans = 0;
 69     while(bfs()) {
 70         ans += dfs(s, inf);
 71     }
 72     return ans;
 73 }
 74 void add(int u, int v, int c) {
 75     e[num] = node(v, head[u], c); head[u] = num++;
 76     e[num] = node(u, head[v], 0); head[v] = num++;
 77 }
 78 void init() {
 79     mem1(head);
 80     num = 0;
 81 }
 82 int main()
 83 {
 84     int T, m, n, x, y, q;
 85     cin>>T;
 86     while(T--) {
 87         init();
 88         scanf("%d%d%d", &n, &m, &q);
 89         int nm = n*m;
 90         s = 2*nm, t = s+1;
 91         for(int i = 1; i<=q; i++) {
 92             scanf("%d%d", &x, &y);
 93             x--, y--;
 94             add(s, x*m+y, 1);
 95         }
 96         for(int i = 0; i<n; i++) {
 97             for(int j = 0; j<m; j++) {
 98                 int ij = i*m+j;
 99                 add(ij, ij+nm, 1);
100                 if(i==0||j==0||i==n-1||j==m-1) {
101                     add(ij+nm, t, 1);
102                 } else {
103                     for(int k = 0; k<4; k++) {
104                         x = i + dir[k][0];
105                         y = j + dir[k][1];
106                         add(ij+nm, x*m+y, 1);
107                     }
108                 }
109             }
110         }
111         if(dinic() == q)
112             cout<<"possible"<<endl;
113         else
114             cout<<"not possible"<<endl;
115     }
116 }
时间: 12-05

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(最大流)

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 Crimewave

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

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

A Plug for UNIX UVA - 753(网络流)

题意:n个插座,m个设备及其插头类型,k种转换器,没有转换器的情况下插头只能插到类型名称相同的插座中,问最少剩几个不匹配的设备 lrj紫书里面讲得挺好的. 先跑一遍floyd,看看插头类型a能否转换为b 然后构造网络 源点为0, 汇点为n + m + 1,源点连插头 容量为1,插座连汇点,容量为1 插头和插座能互相转换的容量为INF,跑一遍最大流 m - 最大流就是答案 顺便粘一下dinic的板子 #include <bits/stdc++.h> using namespace std; in

网络流专栏

最大流 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 (

网络流柱

最大流量 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