UVa 563 Crimewave

想法：
    點與點之間的邊是雙向邊，但是走某一邊後另一邊就不能走了，所以我們把一個點i分成兩個點i和i'，i到i'容量為1，點i建圖的時候：

• cap[i][i']=1
• 假設j在i的上方，cap[i'][j]=1，上下左右依此類推

    然後我們還要有個super source(S)和super sink(T)，把最外面四個邊的點i'連到T，S連到輸入的座標i(也就是銀行的位置)。建完圖後，就是做最大流看結果是否等於銀行的數量即可。

    一開始TLE了，後來用了個vector<int> edge[MAX]來存每個點i能連到哪些點，避免bfs的時候nxt要從0到最後(程式碼81行)，最後時間為1.8s。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	#include <vector>
	using namespace std;
	#define INF 9999999
	#define MAX 2*52*52+10
	vector<int> edge[MAX];
	int cap[MAX][MAX], flow[MAX][MAX];
	int bottleneck[MAX], pre[MAX];
	void BuildGraph(int S, int T, int H, int W);
	int MaxFlow(int S, int T, int H, int W);
	int main()
	{
	int Case, H, W, B, x, y;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d %d", &H, &W, &B);
	int S = 0, // super source
	T = 1; // super sink
	for (int i = 0; i <= 2*(H+1)*W; ++i) edge[i].clear();
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	BuildGraph(S, T, H, W);
	for (int i = 0; i < B; ++i) {
	scanf("%d %d", &x, &y);
	cap[S][(x*H+y)*2] = 1;
	edge[S].push_back((x*H+y)*2);
	}
	if (MaxFlow(S, T, H, W) == B) puts("possible");
	else puts("not possible");
	}
	}
	void BuildGraph(int S, int T, int H, int W)
	{
	for (int i = 1; i <= H; ++i) {
	for (int j = 1; j <= W; ++j) {
	cap[(i*H+j)*2][(i*H+j)*2+1] = 1; // u to u'
	edge[(i*H+j)*2].push_back((i*H+j)*2+1);
	cap[(i*H+j)*2+1][((i-1)*H+j)*2] = 1; // u' to up
	edge[(i*H+j)*2+1].push_back(((i-1)*H+j)*2);
	cap[(i*H+j)*2+1][((i+1)*H+j)*2] = 1; // u' to down
	edge[(i*H+j)*2+1].push_back(((i+1)*H+j)*2);
	cap[(i*H+j)*2+1][(i*H+j-1)*2] = 1; // u' to left
	edge[(i*H+j)*2+1].push_back((i*H+j-1)*2);
	cap[(i*H+j)*2+1][(i*H+j+1)*2] = 1; // u' to right
	edge[(i*H+j)*2+1].push_back((i*H+j+1)*2);
	if (i == 1 || j == 1 || i == H || j == W) {// if on the edge
	cap[(i*H+j)*2+1][T] = 1; // connect u' to the T
	edge[(i*H+j)*2+1].push_back(T);
	}
	}
	}
	}
	int MaxFlow(int S, int T, int H, int W)
	{
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	bottleneck[S] = INF;
	queue<int> Q;
	Q.push(S);
	// bfs
	while (!Q.empty() && !bottleneck[T]) {
	int now = Q.front();
	Q.pop();
	for (int nxt : edge[now]) {
	if (!bottleneck[nxt] && cap[now][nxt] > flow[now][nxt]) {
	Q.push(nxt);
	pre[nxt] = now;
	bottleneck[nxt] = min(bottleneck[now], cap[now][nxt] - flow[now][nxt]);
	}
	}
	}
	if (bottleneck[T] == 0) break;
	for (int now = T; now != S; now = pre[now]) {
	flow[pre[now]][now] += bottleneck[T];
	flow[now][pre[now]] -= bottleneck[T];
	}
	result += bottleneck[T];
	}
	return result;
	}

view raw [UVa] 563 Crimewave.cpp hosted with ❤ by GitHub