BZOJ 1570 JSOI 2008 Blue Mary的旅行 网络流

题目大意

给出1个有向图,每天每人只能做1次飞机。现在给出出发点,终点,和需要走的人数,还有每条航线的限制人数,问最少多少天最慢的人到达终点。

思路

很明显是网络流的模型,至于如何去验证,其实连2分都不用,枚举最少天数,然后每次加1层边进行验证就好了。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
#define MAXE 1000010
#define S 0
#define SS (MAX - 2)
#define T (MAX - 1)
#define INF 0x3f3f3f3f
using namespace std;

struct Edge{
int x, y, z;

void Read() {
scanf("%d%d%d", &x, &y, &z);
}
}edge[MAXE];

struct MaxFlow{
int head[MAX], total;
int _next[MAXE], aim[MAXE], flow[MAXE];
int backup_flow[MAXE];
int deep[MAXE];

MaxFlow():total(1) {}
void Add(int x, int y, int f) {
_next[++total] = head[x];
aim[total] = y;
backup_flow[total] = f;
head[x] = total;
}
void Insert(int x, int y, int f) {
Add(x, y, f);
Add(y, x, 0);
}
bool BFS() {
static queue<int> q;
while(!q.empty()) q.pop();
memset(deep, 0, sizeof(deep));
deep[S] = 1;
q.push(S);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i; i = _next[i])
if(flow[i] && !deep[aim[i]]) {
deep[aim[i]] = deep[x] + 1;
q.push(aim[i]);
if(aim[i] == T) return true;
}
}
return false;
}
int Dinic(int x, int f) {
if(x == T) return f;
int temp = f;
for(int i = head[x]; i; i = _next[i])
if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) {
int away = Dinic(aim[i], min(flow[i], temp));
if(!away) deep[aim[i]] = 0;
flow[i] -= away;
flow[i ^ 1] += away;
temp -= away;
}
return f - temp;
}
}solver;

int points, edges, persons;

int main()
{
cin >> points >> edges >> persons;
for(int i = 1; i <= edges; ++i)
edge[i].Read();
solver.Insert(S, SS, persons);
int now = 0;
for(int i = 1;; ++i) {
for(int j = 1; j <= edges; ++j)
solver.Insert(now + edge[j].x, now + edge[j].y + points, edge[j].z);
solver.Insert(now + points + points, T, INF);
solver.Insert(SS, now + 1, INF);
memcpy(solver.flow, solver.backup_flow, sizeof(solver.flow));
int max_flow = 0;
while(solver.BFS())
max_flow += solver.Dinic(S, INF);
if(max_flow == persons) {
cout << i << endl;
return 0;
}
now += points;
}
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 1570 JSOI 2008 Blue Mary的旅行 网络流

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡