最小割 D. Behind the Wall Samara University ACM ICPC 2016-2017 Quarterfinal Qualification Contest

题目链接:http://codeforces.com/gym/101149/problem/D

题目大意:

堡垒受到攻击。堡垒是n*m的矩阵,矩阵里刚开始都是平地,然后那个数值表示在当前平地上建一面墙需要a[i][j]的时间。目前我们在位置(r, c),我们找一种方法,把(r,c)全部围起来需要的最短时间?

思路:拆点,拆成in和out两个,in和out之间的cap就是a[i][j],然后就是简单的建边拉。

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n") const int maxn = * * + ;
const int INF = 0x3f3f3f3f;
struct Edge {
int from, to, cap, flow;
}; struct Dinic {
int n, m, s, t; ///节点的个数,边的编号,起点,终点
vector<Edge> edges; // 边数的两倍
vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; // BFS使用
int d[maxn]; // 从起点到i的距离
int cur[maxn]; // 当前弧指针
/////////蓝书363
int inq[maxn]; // 是否在队列中
int p[maxn]; // 上一条弧
int a[maxn]; //可改进量 void ClearAll(int n) {
this->n = n; ///这个赋值千万不能忘
for(int i = ; i < n; i++) G[i].clear();
edges.clear();
} void ClearFlow() { ///清除流量,例如蓝书368的UVA11248里面的优化,就有通过清除流量来减少增广次数的
for(int i = ; i < edges.size(); i++) edges[i].flow = ;
} void Reduce() {///直接减少cap,也是减少增广次数的
for(int i = ; i < edges.size(); i++) edges[i].cap -= edges[i].flow;
} void AddEdge(int from, int to, int cap) {
edges.push_back((Edge){from, to, cap, });
edges.push_back((Edge){to, from, , });
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} bool BFS() {///bfs构建层次图
memset(vis, , sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = ;
d[s] = ;
while(!Q.empty()) {
int x = Q.front(); Q.pop();
for(int i = ; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if(!vis[e.to] && e.cap > e.flow) {//只考虑残量网络中的弧
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[t];
} int DFS(int x, int a) {///a表示目前为止,所有弧的最小残量。但是也可以用它来限制最大流量,例如蓝书368LA2957,利用a来保证增量,使得最后maxflow=k
if(x == t || a == ) return a;
int flow = , f;
for(int& i = cur[x]; i < G[x].size(); i++) {//从上次考虑的弧,即已经访问过的就不需要在访问了
Edge& e = edges[G[x][i]];
if(d[x] + == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > ) {
e.flow += f;
edges[G[x][i]^].flow -= f;
flow += f;
a -= f;
if(a == ) break;//如果不在这里终止,效率会大打折扣
}
}
return flow;
}
/**最大流*/
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = ;
while(BFS()) {
memset(cur, , sizeof(cur));
flow += DFS(s, INF);///这里的INF可以发生改变,因为INF保证的是最大残量。但是也可以通过控制残量来控制最大流
}
return flow;
} /**最小割*/
char ch[maxn][maxn];
void Mincut(int x, int y) { /// call this after maxflow求最小割,就是S和T中还存在流量的东西
BFS();///重新bfs一次
for (int i = ; i < x; i++)
for (int j = ; j < y; j++)
ch[i][j] = '.';
int cnt = ;
for(int i = ; i < edges.size(); i++) {
Edge& e = edges[i];
if(vis[e.from] && !vis[e.to] && e.cap >= && e.to - e.from == x * y) {///这里和ISAP不一样
cnt++;
int nx = e.from / y, ny = e.from - nx * y;
ch[nx][ny] = 'X';
//printf("e.from = %d e.to = %d nx = %d ny = %d\n", e.from, e.to, nx, ny);
}
}
//printf("cnt = %d\n", cnt);
for (int i = ; i < x; i++){
for (int j = ; j < y; j++){
printf("%c", ch[i][j]);
}
cout << endl;
} } void debug(){///debug
for (int i = ; i < edges.size(); i++){
printf("u = %d v = %d cap = %d flow = %d\n", edges[i].from + , edges[i].to + , edges[i].cap, edges[i].flow);
}
}
};
Dinic g; int n, m, a, b;
int atlas[maxn][maxn]; int dx[] = {, -, , };
int dy[] = {, , , -};
int in_id(int x, int y){
return x * m + y;
}
int out_id(int x, int y){
return n * m + x * m + y;
} int main(){
scanf("%d%d%d%d", &n, &m, &a, &b);
a--, b--;
for (int i = ; i < n; i++){
for (int j = ; j < m; j++){
scanf("%d", &atlas[i][j]);
}
}
int s = in_id(a, b), t = n * m * + ;
g.ClearAll(t);
for (int i = ; i < n; i++){
for (int j = ; j < m; j++){
if (a == i && b == j) {
for (int k = ; k < ; k++){
int nx = i + dx[k], ny = j + dy[k];
if (nx < || ny < || nx >= n || ny >= m) continue;
g.AddEdge(in_id(i, j), in_id(nx, ny), INF);
}
continue;
}
else {
g.AddEdge(in_id(i, j), out_id(i, j), atlas[i][j]);
if (i == || j == || i == n- || j == m-)
g.AddEdge(out_id(i, j), t, INF);
}
for (int k = ; k < ; k++){
int nx = i + dx[k], ny = j + dy[k];
if (nx < || ny < || nx >= n || ny >= m) continue;
if (nx == a && ny == b) continue;
g.AddEdge(out_id(i, j), in_id(nx, ny), INF);
}
}
}
printf("%d\n", g.Maxflow(s, t));
g.Mincut(n, m);
return ;
}
上一篇:特性Attribute 的使用


下一篇:python的进程与线程(一)