首页 > 代码库 > [BZOJ2324][ZJOI2011][最小费用最大流]营救皮卡丘
[BZOJ2324][ZJOI2011][最小费用最大流]营救皮卡丘
[Problem Description]
皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。
火箭队一共同拥有N个据点,据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为0号据点,一開始K个人都在0号点。
因为火箭队的重重布防,要想摧毁K号据点,必须依照顺序先摧毁1到K-1号据点,而且,假设K-1号据点没有被摧毁,因为防御的连锁性,小智一行不论什么一个人进入据点K,都会被发现,并产生严重后果。因此,在K-1号据点被摧毁之前,不论什么人是不可以经过K号据点的。
为了简化问题,我们忽略战斗环节,小智一行不论什么一个人经过K号据点即觉得K号据点被摧毁。被摧毁的据点依旧是能够被经过的。
K个人是能够分头行动的,仅仅要有不论什么一个人在K-1号据点被摧毁之后,经过K号据点,K号据点就被摧毁了。显然的,仅仅要N号据点被摧毁,皮卡丘就得救了。
野外的道路是不安全的,因此小智一行希望在摧毁N号据点救出皮卡丘的同一时候,使得K个人所经过的道路的长度总和最少。
请你帮助小智设计一个最佳的营救方案吧!
[Algorithm]
最小费用最大流
[Analysis]
题目有几个关键点:
1.每个点都必须有人经过
2.经过j点时,0~j-1必须都经过了才干够
由此能够构造出一个网络流的模型。
因为每一个节点的第一次訪问,必然是由小于它的节点完毕的,所以先用floyd预处理dis[k][i][j]表示i到j仅仅经过小于等于k的点的最短路。建图例如以下
1.S->0 cap=k cost=0
2.i->T cap=1 cost=0
3.S->i+n cap=1 cost=0
4.i+n->j cap=INF cost=dis[j][i][j]
1是用来限制人数的,2则保证每一个点经过一次,因为第一次经过该点时流向了T消耗了流量,所以每一个点给予补充流量,即建图3。4则是从一个刚刚第一次经过的点继续訪问其他点。这样建图能够发现,每一个点的第一次訪问都被转化成了一条从S出发的流且没有交叉,这样能够随意调整訪问顺序,保证了j訪问之前0~j-1都已经訪问过
[Pay Attention]
因为floyd要用邻接矩阵,注意推断重边的情况取最小。
还有要从这样的点至少经过一次的建模中吸取经验
[Code]
/************************************************************** Problem: 2324 User: gaotianyu1350 Language: C++ Result: Accepted Time:392 ms Memory:7620 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #include <iostream> using namespace std; #define MAXN 350 #define MAXM 300000 #define INF 0x3f3f3f3f int point[MAXN], next[MAXM], v[MAXM], flow[MAXM], cap[MAXM], w[MAXM]; int lastedge[MAXN], dis[MAXN]; bool check[MAXN]; int tot = -1; int n, m, people; int map[MAXN][MAXN]; inline void init() { memset(map, 0x7f, sizeof(map)); memset(point, -1, sizeof(point)); memset(next, -1, sizeof(next)); tot = -1; } inline void addedge(int x, int y, int theCap, int theDis) { tot++; next[tot] = point[x]; point[x] = tot; v[tot] = y; flow[tot] = 0; cap[tot] = theCap; w[tot] = theDis; tot++; next[tot] = point[y]; point[y] = tot; v[tot] = x; flow[tot] = 0; cap[tot] = 0; w[tot] = - theDis; } inline int addflow(int s, int t) { int now = t; int ans = INF; while (now != s) { int temp = lastedge[now]; ans = min(ans, cap[temp] - flow[temp]); now = v[lastedge[now] ^ 1]; } now = t; while (now != s) { flow[lastedge[now]] += ans; flow[lastedge[now] ^ 1] -= ans; now = v[lastedge[now] ^ 1]; } return ans; } bool spfa(int s, int t, int &maxflow, int &mincost) { queue<int> q; while (!q.empty()) q.pop(); memset(dis, 0x7f, sizeof(dis)); memset(check, 0, sizeof(check)); dis[s] = 0; check[s] = true; q.push(s); while (!q.empty()) { int now = q.front(); q.pop(); check[now] = false; for (int temp = point[now]; temp != -1; temp = next[temp]) if (flow[temp] < cap[temp] && dis[now] + w[temp] < dis[v[temp]]) { dis[v[temp]] = dis[now] + w[temp]; lastedge[v[temp]] = temp; if (!check[v[temp]]) check[v[temp]] = true, q.push(v[temp]); } } if (dis[t] > INF) return false; int add = addflow(s, t); maxflow += add; mincost += add * dis[t]; return true; } inline int solve(int s, int t) { int maxflow = 0, mincost = 0; while (spfa(s, t, maxflow, mincost)); /*{ int tiaoshi = 1; tiaoshi++; }*/ //printf("mflow :%d\n", maxflow); return mincost; } inline void build(int start, int end) { addedge(start, 0, people, 0); for (int i = 1; i <= n; i++) { addedge(i, end, 1, 0); addedge(start, i + n, 1, 0); //addedge(i, i + n, INF, 0); } for (int k = 0; k <= n; k++) for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) if (i != j) { if (map[i][k] < INF && map[k][j] < INF) map[i][j] = min(map[i][j], map[i][k] + map[k][j]); if (k == j && i < j && map[i][j] < INF) addedge(i == 0 ? 0 : i + n, j, INF, map[i][j]); } } int main() { //freopen("input.txt", "r", stdin); init(); scanf("%d%d%d", &n, &m, &people); for (int i = 1; i <= m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); if (z < map[x][y]) map[x][y] = map[y][x] = z; } build(2 * n + 1, 2 * n + 2); printf("%d\n", solve(2 * n + 1, 2 * n + 2)); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。