51nod 2887 抓小偷 平面图最小割转换成最短路

平面图最小割转换成最短路"/>

51nod 2887 抓小偷 平面图最小割转换成最短路

首先是n^2m的复杂度的最小割 果断超时了 。。网上一搜是需要转换成最短路的

#include<iostream>
#include<cstring>
#include<queue>#define INF 0x3f3f3f3fusing namespace std;const int N = 410 * 410,M = N * 2;int head[N],to[M],last[M],c[M],cnt;
void add(int a,int b,int c1){to[++cnt] = b;c[cnt] = c1;last[cnt] = head[a];head[a] = cnt;to[++cnt] = a;c[cnt] = 0;last[cnt] = head[b];head[b] = cnt;
}int S,T;int d[N],cur[N];
bool bfs(){memset(d,0,sizeof d);d[S] = 1;queue<int>q;q.push(S);cur[S] = head[S];while(q.size()){int p = q.front();q.pop();for(int i = head[p]; i != -1; i = last[i]){int j = to[i];if(!d[j] && c[i]){d[j] = d[p] + 1;q.push(j);cur[j] = head[j];if(j == T) return true;}}}return d[T] > 0;
}int dfs(int x,int sum){if(x == T) return sum;int used = 0;for(int i = cur[x]; i != -1; i = last[i]){int j = to[i];cur[x] = i;if(d[j] == d[x] + 1 && c[i]){int dd = dfs(j,min(sum - used,c[i]));c[i] -= dd;c[i ^ 1] += dd;used += dd;}}if(used == 0) d[x] = -1;return used;
}int dinic(){int sum = 0;while(bfs()){sum += dfs(S,INF);}return sum;
}int main(){int n;cin >> n;memset(head,-1,sizeof head);cnt = 1;S = 0,T = n * n + 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){int x;scanf("%d",&x);if(i + 1 <= n) add((i - 1) * n + j,i * n + j,x);if(j + 1 <= n) add((i - 1) * n + j,(i - 1) * n + j + 1,x);}}add(S,1,INF);add(n * n,T,INF);cout << dinic() << endl;return 0;
}

如何转换成求最短路的呢 每个平面图都对应一个图 每一个S -> T 的路径 都是一条割

#include<iostream>
#include<cstring>
#include<queue>
#include<utility>
#define x first
#define y second
#define INF 0x3f3f3f3fusing namespace std;const int N = 410 * 410,M = N * 2;
typedef pair<int,int> PII;int head[N],to[M],last[M],w[M],cnt;
void add(int a,int b,int c){to[++cnt] = b;w[cnt] = c;last[cnt] = head[a];head[a] = cnt;
}int a[410][410];
int S,T;
int dist[N],flag[N];
int dij(){memset(dist,0x3f,sizeof dist);memset(flag,0,sizeof flag);priority_queue<PII,vector<PII>,greater<PII> > q;q.push({0,S});dist[S] = 0;while(q.size()){PII p = q.top();q.pop();if(flag[p.y]) continue;flag[p.y] = 1;for(int i = head[p.y]; i != -1; i = last[i]){int j = to[i];if(dist[j] > dist[p.y] + w[i]){dist[j] = dist[p.y] + w[i];q.push({dist[j],j});}}}return dist[T];
}int main(){int n;cin >> n;memset(head,-1,sizeof head);cnt = 1;S = 0,T = n * n + 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){scanf("%d",&a[i][j]);}}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(j == 1 && i != 1){add((i - 2) * n + j + 1,T,a[i - 1][j]);}if(i == n && j != n){add((i - 2) * n + j + 1,T,a[i][j]);}if(i == 1 && j != 1){add(S,(i - 1) * n + j,a[i][j - 1]);}if(j == n && i != n){add(S,(i - 1) * n + j,a[i][j]);}if(i + 1 < n){add((i - 1) * n + j,i * n + j,a[i + 1][j - 1]);}if(j - 1 > 1){add((i - 1) * n + j,(i - 1) * n + j - 1,a[i][j - 1]);}}}cout << dij();return 0;
}