给你n种菜， 每一种可以开始吃的时间不一样， 结束的时间也不一样。 求每种菜吃的时间都相同的最大的时间。时间的范围是0-10000。
看到这个题明显可以想到网络流， 但是时间的范围明显不允许我们把对每一个时间都连边。
那么我们可以对时间的区间连边， 对于一个区间， 如果一盘菜的开始时间>=这个区间的左端点， 结束时间小于右端点， 那么这盘菜就对这个时间段连边， 权值inf。然后每个时间段对汇点t连边， 权值为这段时间的长度。 源点s向每个菜连边， 权值为二分枚举的时间长度， 然后跑最大流， 看结果是否等于n*x， x是枚举的时间。
具体对时间区间连边的方法可以看代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 4e5+5; 20 int q[maxn*2], head[maxn*2], dis[maxn/10], s, t, used[10005], a[105], b[105], n, cnt, num, from; 21 struct node 22 { 23 int to, nextt, c; 24 node(){} 25 node(int to, int nextt, int c):to(to), nextt(nextt), c(c){} 26 }e[maxn*2]; 27 void init() { 28 num = from = cnt = 0; 29 mem1(head); 30 } 31 void add(int u, int v, int c) { 32 e[num] = node(v, head[u], c); head[u] = num++; 33 e[num] = node(u, head[v], 0); head[v] = num++; 34 } 35 int bfs() { 36 mem(dis); 37 dis[s] = 1; 38 int st = 0, ed = 0; 39 q[ed++] = s; 40 while(st<ed) { 41 int u = q[st++]; 42 for(int i = head[u]; ~i; i = e[i].nextt) { 43 int v = e[i].to; 44 if(!dis[v]&&e[i].c) { 45 dis[v] = dis[u]+1; 46 if(v == t) 47 return 1; 48 q[ed++] = v; 49 } 50 } 51 } 52 return 0; 53 } 54 int dfs(int u, int limit) { 55 if(u == t) { 56 return limit; 57 } 58 int cost = 0; 59 for(int i = head[u]; ~i; i = e[i].nextt) { 60 int v = e[i].to; 61 if(e[i].c&&dis[v] == dis[u]+1) { 62 int tmp = dfs(v, min(limit-cost, e[i].c)); 63 if(tmp>0) { 64 e[i].c -= tmp; 65 e[i^1].c += tmp; 66 cost += tmp; 67 if(cost == limit) 68 break; 69 } else { 70 dis[v] = -1; 71 } 72 } 73 } 74 return cost; 75 } 76 int dinic() { 77 int ans = 0; 78 while(bfs()) { 79 ans += dfs(s, inf); 80 } 81 return ans; 82 } 83 int check(int x) { 84 init(); 85 for(int i = 0; i<10001; i++) { 86 if(used[i]) { 87 int flag = 1; 88 for(int j = 0; j<n; j++) { 89 if(a[j]<=from&&i<=b[j]) { 90 if(flag) { 91 add(s, ++cnt, i-from); //起点对区间连边。 92 flag = 0; 93 } 94 add(cnt, j+300, inf); //区间对每一个在它范围内的菜连边 95 } 96 } 97 from = i; 98 } 99 } 100 for(int i = 0; i<n; i++) { 101 add(i+300, t, x); 102 } 103 int ans = dinic(); 104 if(ans == x*n) 105 return 1; 106 return 0; 107 } 108 int main() 109 { 110 cin>>n; 111 for(int i = 0; i<n; i++) { 112 scanf("%d%d", &a[i], &b[i]); 113 used[a[i]] = 1; 114 used[b[i]] = 1; 115 } 116 s = 0, t = 402; 117 int l = 0, r = 10001; 118 while(r>l+1) { 119 int mid = l+r>>1; 120 if(check(mid)) { 121 l = mid; 122 } else { 123 r = mid; 124 } 125 } 126 cout<<l*n<<endl; 127 }