poj1698:http://poj.org/problem?id=1698
题意：爱丽丝要拍电影，有n部电影，规定爱丽丝每部电影在每个礼拜只有固定的几天可以拍电影，只可以拍前面w个礼拜，并且这部电影要拍d天,问爱丽丝能不能拍完所有的电影。
题解：这里有一点技巧，一开始我想到的就是每一天放在一起，实际上，要考虑时间问题，就必须把不同星期的每一天区分开来，那样建图才是正确的。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define INF 100000000
using namespace std;
const int N=;
const int M=;
struct Node{
int v;
int f;
int next;
}edge[M];
int n,m,u,v,cnt,sx,ex;
int head[N],pre[N];
int val1[N],val2[N];//根据题目要求申请
void init(){
cnt=;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w){
edge[cnt].v=v;
edge[cnt].f=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
bool BFS(){
memset(pre,,sizeof(pre));
pre[sx]=;
queue<int>Q;
Q.push(sx);
while(!Q.empty()){
int d=Q.front();
Q.pop();
for(int i=head[d];i!=-;i=edge[i].next ){
if(edge[i].f&&!pre[edge[i].v]){
pre[edge[i].v]=pre[d]+;
Q.push(edge[i].v);
}
}
}
return pre[ex]>;
}
int dinic(int flow,int ps){
int f=flow;
if(ps==ex)return f;
for(int i=head[ps];i!=-;i=edge[i].next){
if(edge[i].f&&pre[edge[i].v]==pre[ps]+){
int a=edge[i].f;
int t=dinic(min(a,flow),edge[i].v);
edge[i].f-=t;
edge[i^].f+=t;
flow-=t;
if(flow<=)break;
} }
if(f-flow<=)pre[ps]=-;
return f-flow;
}
int solve(){
int sum=;
while(BFS())
sum+=dinic(INF,sx);
return sum;
}
int a[];
int main() {
int T,k,temp,sum,tt=,t1,t2;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);tt=;
init();sum=;sx=,ex=;
for(int i=;i<=n; i++) {
for(int j=;j<=;j++){
scanf("%d",&a[j]);
}
scanf("%d%d",&t1,&t2);
sum+=t1;
for(int j=;j<=;j++){
if(a[j]==){
for(int k=;k<t2;k++)
add(i+,k*+j,);
}
}
add(,i+,t1);
}
for(int i=;i<=;i++)
add(i,,);
if(sum==solve()){
printf("Yes\n");
}
else printf("No\n"); }
return ;
}