题意：已知n（n <= 150）个城市和m（m <= 5000）个航班，每个航班有出发地、到达地、乘坐人数、起飞时间和降落时间（时间用时和分表示），求从一个指定城市出发，去往另一个指定城市在规定的最晚时间前（包括最晚时间）可以到达的最大人数（换航班的间隔至少需要30分钟）。
分析：
1、首先最大流模板中是不考虑时间因素的，从一个点分别向不同的方向出发是同时的，所以不能以城市为最大流模板中的顶点。
2、为了考虑时间因素，以航班为顶点，以城市为边，将同一个航班拆成两个点i与i + m（拆点法），则i -> i + m的容量为航班的乘坐人数。（以航班为顶点，忽视了容量，因此要补充。）
3、若两趟航班之间可以转（即第一个航班的降落时间与第二个航班的起飞时间至少相差30分钟），那么就将第一个航班的i + m连到第二个航班的i上去，容量为正无穷。（此处因为不确定容量，但是有同一航班间的容量限制，所以可以设为正无穷）
4、出发城市和到达城市也视为顶点，则：所有出发点为出发城市的航班，将出发城市与该航班的i间建边，所有终点为到达城市的航班，且到达时间在规定最晚时间之前的，将该航班的i + m与到达城市间建边。容量均为正无穷；（可视为城市中可以有很多人上这个航班，因此不确定容量，但是有同一航班间的容量限制，所以可以设为正无穷）
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 10000 + 10; const int MAXT = 10000 + 10; using namespace std; struct Edge{ int from, to, cap, flow; Edge(int f, int t, int c, int fl):from(f), to(t), cap(c), flow(fl){} }; struct Dinic{ int n, m, s, t; vector<Edge> edges; vector<int> G[MAXN]; bool vis[MAXN]; int d[MAXN]; int cur[MAXN]; void init(int w){//d数组可以不初始化 edges.clear(); for(int i = 0; i < w; ++i) G[i].clear(); } void AddEdge(int from, int to, int cap){ edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS(){ memset(vis, false, sizeof vis); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); ++i){ Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow){ vis[e.to] = true; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a){ if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); ++i){ Edge& e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to, Min(a, e.cap - e.flow))) > 0){ e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow(int s, int t){ this -> s = s; this -> t = t; int flow = 0; while(BFS()){ memset(cur, 0, sizeof cur); flow += DFS(s, INT_INF); } return flow; } }di;//# map<string, int> ma; int id; int get_id(string x){ if(!ma.count(x)) return ma[x] = id++;//加return更快 return ma[x];//#ma.count() } int get_time(char s[]){ return ((s[0] - '0') * 10 + s[1] - '0') * 60 + (s[2] - '0') * 10 + s[3] - '0'; } struct Node{ int aid, bid, c, atime, btime; }num[MAXN]; int main(){ int n; while(scanf("%d", &n) == 1) { ma.clear(); id = 0; char st[10], en[10]; scanf("%s%s", st, en); int stid = get_id(st);//string对char*的构造函数 int enid = get_id(en); scanf("%s", st); int m; scanf("%d", &m); int t = get_time(st); int cnt = 0; for(int i = 1; i <= m; ++i){ scanf("%s%s", st, en); num[i].aid = get_id(st); num[i].bid = get_id(en); scanf("%d%s%s", &num[i].c, st, en); num[i].atime = get_time(st); num[i].btime = get_time(en); } di.init(2 * m + 10); for(int i = 1; i <= m; ++i){ di.AddEdge(i, i + m, num[i].c);//每个航班拆成两个点，i和i+m if(num[i].aid == stid) di.AddEdge(0, i, INT_INF);//源点和汇点也看做点，标号为0和2*m+1 if(num[i].bid == enid && num[i].btime <= t) di.AddEdge(i + m, 2 * m + 1, INT_INF); for(int j = 1; j <= m; ++j){ if(i == j) continue; if(num[i].bid == num[j].aid && num[j].atime - num[i].btime >= 30){ di.AddEdge(i + m, j, INT_INF);//i+m } } } printf("%d\n", di.Maxflow(0, 2 * m + 1)); } return 0; }