题目描述：有m(1000)个钢琴，p(2000)个人，第i个钢琴要在[ai,bi]天之间的某一天被运送，(1<=ai,bi<=100)，一个钢琴需要2个人运送(即每天最多可以有p/2个钢琴被运送)。
问：
能否不在周六日运完。
如果上述不能，加上周六日能否运完。
解题报告：
一开始的想法比较弱：
源点s，汇点t。
源点连接每个钢琴，容量1
问：
能否不在周六日运完。
如果上述不能，加上周六日能否运完。
解题报告：
一开始的想法比较弱：
源点s，汇点t。
源点连接每个钢琴，容量1
新浪博客
，表示一个钢琴只能运送一次。
每个钢琴连接[ai,bi]一共bi-a1+1个点，容量1，表示这个钢琴只能在[ai,bi]之前选一天。
每一天的点连接汇点，容量p/2，表示每一天最多运送p/2个钢琴。
周六日的限制就在于天数的节点剪掉周六日的节点即可。
看最大流是否等于钢琴的个数即可（表示所有的钢琴都被运送完）；
这样的话，点数就有m+100+2个，边数最坏可以由m*100个，
即1100个点，10^5条边，太多了，不过POJ还能过。。
优化的建模方法如下：
源点连接每一天（不连周六日就是第一问），容量为p/2，表示每一天都可以有p/2个钢琴被搬运。
对于每一天i，连接i到汇点，容量为以i为结尾的钢琴。
对于每一天i，连接i到i+1，容量为i到i+1被m个钢琴区间覆盖的次数。
这样，每个钢琴只要在最后一天前能够凑到一个人就算被搬运了。
而由于i到i+1容量的限制，保证了为a钢琴凑得人不会多于，即不会给不相交区间的b钢琴使用。
这样最多一共就102个点，299条边，效率提高了很多很多。
看最大流是否等于m即可，代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define Max 0x1fffffff
#define SIZE 200
vector<pair<int, int> > jeo;
struct edge{int from, to, val, next;}e[14000000];
int v[SIZE], que[SIZE], dis[SIZE], cnt, cur[SIZE];
void insert(int from, int to, int va)
{
}
bool bfs(int n, int s, int t)
{
}
int Dinic(int n, int s, int t)
{
每个钢琴连接[ai,bi]一共bi-a1+1个点，容量1，表示这个钢琴只能在[ai,bi]之前选一天。
每一天的点连接汇点，容量p/2，表示每一天最多运送p/2个钢琴。
周六日的限制就在于天数的节点剪掉周六日的节点即可。
看最大流是否等于钢琴的个数即可（表示所有的钢琴都被运送完）；
这样的话，点数就有m+100+2个，边数最坏可以由m*100个，
即1100个点，10^5条边，太多了，不过POJ还能过。。
优化的建模方法如下：
源点连接每一天（不连周六日就是第一问），容量为p/2，表示每一天都可以有p/2个钢琴被搬运。
对于每一天i，连接i到汇点，容量为以i为结尾的钢琴。
对于每一天i，连接i到i+1，容量为i到i+1被m个钢琴区间覆盖的次数。
这样，每个钢琴只要在最后一天前能够凑到一个人就算被搬运了。
而由于i到i+1容量的限制，保证了为a钢琴凑得人不会多于，即不会给不相交区间的b钢琴使用。
这样最多一共就102个点，299条边，效率提高了很多很多。
看最大流是否等于m即可，代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define Max 0x1fffffff
#define SIZE 200
vector<pair<int, int> > jeo;
struct edge{int from, to, val, next;}e[14000000];
int v[SIZE], que[SIZE], dis[SIZE], cnt, cur[SIZE];
void insert(int from, int to, int va)
{
}
bool bfs(int n, int s, int t)
{
}
int Dinic(int n, int s, int t)
{